{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Merge Intervals"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: merge"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #合并区间"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>以数组 <code>intervals</code> 表示若干个区间的集合，其中单个区间为 <code>intervals[i] = [start<sub>i</sub>, end<sub>i</sub>]</code> 。请你合并所有重叠的区间，并返回&nbsp;<em>一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间</em>&nbsp;。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>intervals = [[1,3],[2,6],[8,10],[15,18]]\n",
    "<strong>输出：</strong>[[1,6],[8,10],[15,18]]\n",
    "<strong>解释：</strong>区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例&nbsp;2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>intervals = [[1,4],[4,5]]\n",
    "<strong>输出：</strong>[[1,5]]\n",
    "<strong>解释：</strong>区间 [1,4] 和 [4,5] 可被视为重叠区间。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= intervals.length &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>intervals[i].length == 2</code></li>\n",
    "\t<li><code>0 &lt;= start<sub>i</sub> &lt;= end<sub>i</sub> &lt;= 10<sup>4</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [merge-intervals](https://leetcode.cn/problems/merge-intervals/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [merge-intervals](https://leetcode.cn/problems/merge-intervals/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,3],[2,6],[8,10],[15,18]]', '[[1,4],[4,5]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBattleships(self, board: List[List[str]]) -> int:\n",
    "        m,n = len(board),len(board[0])\n",
    "        parent = {(x,y):(x,y) for x  in range(m) for y in range(n) if board[x][y] == 'X'}\n",
    "        rank = {(x,y):1 for x  in range(m) for y in range(n) if board[x][y] == 'X'}\n",
    "        self.count = 0\n",
    "        def find(i):\n",
    "            if parent[i] != i:\n",
    "                parent[i] = find(parent[i])\n",
    "            return parent[i]\n",
    "        def merge(i,j):\n",
    "            ri,rj = find(i),find(j)\n",
    "            if ri != rj:\n",
    "                if rank[rj] > rank[ri]:\n",
    "                    ri,rj = rj,ri\n",
    "                parent[rj] = ri\n",
    "                rank[ri] += rank[rj]\n",
    "                self.count -= 1\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if board[i][j] == 'X':\n",
    "                    self.count += 1\n",
    "                    for x,y in [[i+1,j],[i,j-1]]:\n",
    "                        if 0<=x<m and 0<=y<n and board[x][y] == 'X':\n",
    "                            merge((x,y),(i,j))\n",
    "        return self.count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulArray(self, n: int) -> List[int]:\n",
    "        ans = []\n",
    "\n",
    "        #触底\n",
    "        if n == 1:\n",
    "            ans.append(1)\n",
    "            return ans\n",
    "\n",
    "        #递归地将子问题解决\n",
    "        left_beautiful_arry = self.beautifulArray((n + 1) // 2)\n",
    "        right_beautiful_arry = self.beautifulArray(n // 2)\n",
    "\n",
    "        #merge:\n",
    "        for val in left_beautiful_arry:\n",
    "            # 将左侧数组映射为奇数\n",
    "            ans.append(val * 2 - 1)\n",
    "        for val in right_beautiful_arry:\n",
    "            # 将右侧数组映射为偶数\n",
    "            ans.append(val * 2)\n",
    "        return ans\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulArray(self, n: int) -> List[int]:\n",
    "        ans = []\n",
    "\n",
    "        #触底\n",
    "        if n == 1:\n",
    "            ans.append(1)\n",
    "            return ans\n",
    "\n",
    "        #递归地将子问题解决\n",
    "        left_beautiful_arry = self.beautifulArray((n + 1) // 2)\n",
    "        right_beautiful_arry = self.beautifulArray(n // 2)\n",
    "\n",
    "        #merge:\n",
    "        for val in left_beautiful_arry:\n",
    "            # 将左侧数组映射为奇数\n",
    "            ans.append(val * 2 - 1)\n",
    "        for val in right_beautiful_arry:\n",
    "            # 将右侧数组映射为偶数\n",
    "            ans.append(val * 2)\n",
    "            \n",
    "        return ans\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulArray(self, n: int) -> List[int]:\n",
    "        ans=[i for i in range(1,n+1)]\n",
    "        def merge(ans):\n",
    "            if len(ans)==2 or len(ans)==1:\n",
    "                return ans\n",
    "            A=[]\n",
    "            B=[]\n",
    "            for i in range(len(ans)):     \n",
    "                if i%2==0:\n",
    "                    A.append(ans[i])\n",
    "                else:\n",
    "                    B.append(ans[i])\n",
    "            return merge(A)+merge(B)\n",
    "        return merge(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.H = {}\n",
    "\n",
    "    def beautifulArray(self, n: int) -> List[int]:\n",
    "        ans = []\n",
    "\n",
    "        #触底\n",
    "        if n == 1:\n",
    "            ans.append(1)\n",
    "            return ans\n",
    "        if n in self.H:\n",
    "            return self.H[n]\n",
    "\n",
    "        #递归地将子问题解决\n",
    "        left_beautiful_arry = self.beautifulArray((n + 1) // 2)\n",
    "        right_beautiful_arry = self.beautifulArray(n // 2)\n",
    "\n",
    "        #merge:\n",
    "        for val in left_beautiful_arry:\n",
    "            # 将左侧数组映射为奇数\n",
    "            ans.append(val * 2 - 1)\n",
    "        for val in right_beautiful_arry:\n",
    "            # 将右侧数组映射为偶数\n",
    "            ans.append(val * 2)\n",
    "\n",
    "        #放入哈希表\n",
    "        self.H[n] = ans\n",
    "        return ans\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dprogramming(self, k, prices):\n",
    "        \"\"\"\n",
    "        :type k: int\n",
    "        :type prices: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if k <= 0 or len(prices) == 0:\n",
    "            return 0\n",
    "        l = [[0 for _ in range(k+1)] for _ in range(len(prices))]\n",
    "        g = [[0 for _ in range(k+1)] for _ in range(len(prices))]\n",
    "        for i in range(1,len(prices)):\n",
    "            diff = prices[i] - prices[i-1]\n",
    "            for j in range(1,k+1):\n",
    "                l[i][j] = max(g[i-1][j-1] + max(0, diff), l[i-1][j] + diff)\n",
    "                g[i][j] = max(l[i][j], g[i-1][j])\n",
    "        return g[-1][-1]\n",
    "    \n",
    "    def maxProfit(self, k, prices):\n",
    "        \"\"\"\n",
    "        :type k: int\n",
    "        :type prices: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if len(prices) < 2:\n",
    "            return 0\n",
    "        # 按照递增序列分段\n",
    "        sums = []\n",
    "        # 跟踪上一个递增序列的最小值\n",
    "        lasti = 0\n",
    "        for i in range(1, len(prices)):\n",
    "            if prices[i] < prices[i-1]:\n",
    "                if prices[i-1] - prices[lasti] > 0:\n",
    "                    sums.append((prices[lasti], prices[i-1]))\n",
    "                # 将递增序列的前端点置为当前节点\n",
    "                lasti = i\n",
    "        # 如果递增直至最后一个元素，需要额外处理\n",
    "        if prices[-1] - prices[lasti] > 0:\n",
    "            sums.append((prices[lasti], prices[-1]))\n",
    "        # print(\"sums\", sums)\n",
    "        # k次交易的profit一定大于k-1次，所以，\n",
    "        # 只需要求k次的即可\n",
    "        if k >= len(sums):\n",
    "            return sum([i[1]-i[0] for i in sums])\n",
    "        else:\n",
    "            np = []\n",
    "            for a, b in sums:\n",
    "                np.append(a)\n",
    "                np.append(b)\n",
    "            return self.dprogramming(k, np)\n",
    "        \"\"\"\n",
    "        window = len(sums) - k\n",
    "        ksums = [i for i in sums]\n",
    "        # 依次递减交易量\n",
    "        while window > 0:\n",
    "            # 缩减到k词交易带来的损失\n",
    "            ksums = self.shrink1trade(ksums)\n",
    "            #sums = [i for i in ksums]\n",
    "            #ksums.clear()\n",
    "            window -= 1\n",
    "        return sum([i[1]-i[0] for i in ksums])\n",
    "        \"\"\"\n",
    "\n",
    "    def shrink1trade(self, profits):\n",
    "        \"\"\"减少一笔交易的最大收益\n",
    "        \n",
    "        减少一笔交易包括剔除一笔或者合并相邻两笔（中间不交易）\n",
    "        \"\"\"\n",
    "        # print(\"\\t======\", profits)\n",
    "        ploss = 10**10\n",
    "        pi = 0\n",
    "        for i in range(len(profits)):\n",
    "            if ploss > profits[i][1] - profits[i][0]:\n",
    "                ploss = profits[i][1] - profits[i][0]\n",
    "                pi = i\n",
    "            if i + 1 < len(profits):\n",
    "                mergeloss = profits[i][1] - profits[i+1][0]\n",
    "                if ploss > mergeloss:\n",
    "                    ploss = mergeloss\n",
    "                    pi = i\n",
    "        np = []\n",
    "        i = 0\n",
    "        while i < len(profits):\n",
    "            if pi == i:\n",
    "                if ploss != profits[i][1] - profits[i][0]:\n",
    "                    # 合并\n",
    "                    np.append((profits[i][0], profits[i+1][1]))\n",
    "                    i += 1\n",
    "                else:\n",
    "                    # 删除，不需要处理\n",
    "                    pass\n",
    "            else:\n",
    "                np.append((profits[i][0], profits[i][1]))\n",
    "            i += 1\n",
    "        return np"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def BSTSequences(self, root: TreeNode) -> List[List[int]]:\n",
    "        def merge(arr1, arr2):\n",
    "            if not arr1: return [arr2]\n",
    "            if not arr2: return [arr1]\n",
    "            res = []\n",
    "            nums = merge(arr1[1:], arr2)\n",
    "            for arr in nums:\n",
    "                res.append([arr1[0]]+arr)\n",
    "            nums = merge(arr1, arr2[1:])\n",
    "            for arr in nums:\n",
    "                res.append([arr2[0]]+arr)\n",
    "            return res\n",
    "\n",
    "        if not root: return [[]]\n",
    "        arr1 = self.BSTSequences(root.left)\n",
    "        arr2 = self.BSTSequences(root.right)\n",
    "        l1 = len(arr1[0])\n",
    "        l2 = len(arr2[0])\n",
    "        res = []\n",
    "        if l1 and l2:\n",
    "            for i in arr1:\n",
    "                for j in arr2:\n",
    "                    for arr in merge(i, j):\n",
    "                        res.append([root.val] + arr)\n",
    "        elif l1:\n",
    "            for i in arr1:\n",
    "                res.append([root.val] + i)\n",
    "        elif l2:\n",
    "            for i in arr2:\n",
    "                res.append([root.val] + i)\n",
    "        else:\n",
    "            res = [[root.val]]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def BSTSequences(self, root: TreeNode) -> List[List[int]]:\n",
    "        if root is None:\n",
    "            return [[]]\n",
    "        left_seqs = self.BSTSequences(root.left) if root.left is not None else [[]]\n",
    "        right_seqs = self.BSTSequences(root.right) if root.right is not None else [[]]\n",
    "        seqs = []\n",
    "        for l in left_seqs:\n",
    "            for r in right_seqs:\n",
    "                seqs.extend(self.merge_sequences(l, 0, r, 0, [root.val]))\n",
    "        return seqs\n",
    "\n",
    "    def merge_sequences(\n",
    "        self,\n",
    "        left: List[int],\n",
    "        left_index: int,\n",
    "        right: List[int],\n",
    "        right_index: int,\n",
    "        temp_seq: List[int],\n",
    "    ) -> List[List[int]]:\n",
    "        if left_index == len(left) and right_index == len(right):\n",
    "            return [temp_seq]\n",
    "        if left_index == len(left):\n",
    "            return [temp_seq + right[right_index:]]\n",
    "        if right_index == len(right):\n",
    "            return [temp_seq + left[left_index:]]\n",
    "        return self.merge_sequences(\n",
    "            left, left_index + 1, right, right_index, temp_seq + [left[left_index]]\n",
    "        ) + self.merge_sequences(\n",
    "            left, left_index, right, right_index + 1, temp_seq + [right[right_index]]\n",
    "        )"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "from itertools import product\n",
    "class Solution:\n",
    "    def BSTSequences(self, root: TreeNode) -> List[List[int]]:\n",
    "        res = list()\n",
    "        if root is None:\n",
    "            res.append(list())\n",
    "            return res\n",
    "        left = self.BSTSequences(root.left)\n",
    "        right = self.BSTSequences(root.right)\n",
    "\n",
    "        def merge(i: int, j: int, l: list[int], r: list[int], cur: list[int], m: int, n: int):\n",
    "            if i == m and j == n:\n",
    "                yield cur.copy()\n",
    "            if i < m:\n",
    "                cur.append(l[i])\n",
    "                yield from merge(i + 1, j, l, r, cur, m, n)\n",
    "                cur.pop()\n",
    "            if j < n:\n",
    "                cur.append(r[j])\n",
    "                yield from merge(i, j + 1, l, r, cur, m, n)\n",
    "                cur.pop()\n",
    "        \n",
    "        for l, r in product(left, right):\n",
    "            res.extend(merge(0, 0, l, r, [root.val], len(l), len(r)))\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    class DisjointSet:\n",
    "        def __init__(self, n):\n",
    "            self.f = list(range(n))\n",
    "        \n",
    "        def find(self, x):\n",
    "            if x == self.f[x]:\n",
    "                return x\n",
    "            self.f[x] = self.find(self.f[x])\n",
    "            return self.f[x]\n",
    "        \n",
    "        def merge(self, x, y):\n",
    "            self.f[self.find(x)] = self.find(y)\n",
    "    \n",
    "    # 单元格性质建图\n",
    "    def hasValidPath(self, grid: List[List[int]]) -> bool:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        patterns = [0, 0b1010, 0b0101, 0b1100, 0b0110, 0b1001, 0b0011]\n",
    "        dirs = [(-1, 0), (0, 1), (1, 0), (0, -1)]\n",
    "        ds = Solution.DisjointSet(m * n)\n",
    "        \n",
    "        def getId(x, y):\n",
    "            return x * n + y\n",
    "\n",
    "        def handler(x, y):\n",
    "            pattern = patterns[grid[x][y]]\n",
    "            for i, (dx, dy) in enumerate(dirs):\n",
    "                if (pattern & (1 << i)) > 0:\n",
    "                    sx, sy = x + dx, y + dy\n",
    "                    if 0 <= sx < m and 0 <= sy < n and (patterns[grid[sx][sy]] & (1 << ((i + 2) % 4))) > 0:\n",
    "                        ds.merge(getId(x, y), getId(sx, sy))\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                handler(i, j)\n",
    "        \n",
    "        return ds.find(getId(0, 0)) == ds.find(getId(m - 1, n - 1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class DisjoinSet:\n",
    "\n",
    "    def __init__(self, n):\n",
    "        self.f = list(range(n))\n",
    "\n",
    "    def find(self, x):\n",
    "        if x == self.f[x]:\n",
    "            return x\n",
    "        self.f[x] = self.find(self.f[x])\n",
    "        return self.f[x]\n",
    "    def merge(self, x, y):\n",
    "        self.f[self.find(x)] = self.find(y)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[int]]) -> bool:\n",
    "        n, m = len(grid), len(grid[0])\n",
    "        ds = DisjoinSet(n * m)\n",
    "        patterns = [0, 0b1010, 0b0101, 0b1100, 0b0110, 0b1001, 0b0011]\n",
    "        dirs = [(-1, 0), (0, 1), (1, 0), (0, -1)]\n",
    "        \n",
    "        def getId(x, y):\n",
    "            return x * m + y\n",
    "\n",
    "        def handler(x, y):\n",
    "\n",
    "            pattern = patterns[grid[x][y]]\n",
    "\n",
    "            for i, (dx, dy) in enumerate(dirs):\n",
    "                if (pattern & (1 << i)) > 0:\n",
    "                    sx, sy = x + dx, y + dy\n",
    "                    if 0 <= sx < n and 0 <= sy < m and (patterns[grid[sx][sy]] & (1 << (i + 2) % 4)) > 0:\n",
    "                        ds.merge(getId(x, y), getId(sx, sy))\n",
    "        \n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "\n",
    "                handler(i , j)\n",
    "        \n",
    "        return ds.find(getId(0, 0)) == ds.find(getId(n - 1, m - 1))\n",
    "        # n, m = len(grid), len(grid[0])\n",
    "        # ds = DisjoinSet(n * m)\n",
    "\n",
    "        # def getId(x, y):\n",
    "        #     return x * m + y\n",
    "\n",
    "        # def detectL(x, y):\n",
    "        #     if 0 <= x < n and 0 <= y - 1 < m and grid[x][y - 1] in set([1, 4, 6]):\n",
    "        #         ds.merge(getId(x, y), getId(x, y - 1))\n",
    "        # def detectR(x, y):\n",
    "        #     if 0 <= x < n and 0 <= y + 1 < m and grid[x][y + 1] in set([1, 3, 5]):\n",
    "        #         ds.merge(getId(x, y), getId(x, y + 1))\n",
    "\n",
    "        # def detectU(x, y):\n",
    "        #     if 0 <= x - 1 < n and 0 <= y < m and grid[x - 1][y] in set([2, 3, 4]):\n",
    "        #         ds.merge(getId(x, y), getId(x - 1, y ))\n",
    "\n",
    "        # def detectD(x, y):\n",
    "        #     if 0 <= x + 1 < n and 0 <= y < m and grid[x + 1][y] in set([2, 5, 6]):\n",
    "        #         ds.merge(getId(x, y), getId(x + 1, y ))\n",
    "\n",
    "        # def handler(x, y):\n",
    "        #     if grid[x][y] == 1:\n",
    "        #         detectL(x, y)\n",
    "        #         detectR(x, y)\n",
    "        #     elif grid[x][y] == 2:\n",
    "        #         detectU(x, y)\n",
    "        #         detectD(x, y)\n",
    "        #     elif grid[x][y] == 3:\n",
    "        #         detectL(x, y)\n",
    "        #         detectD(x, y)\n",
    "        #     elif grid[x][y] == 4:\n",
    "        #         detectR(x, y)\n",
    "        #         detectD(x, y)\n",
    "        #     elif grid[x][y] == 5:\n",
    "        #         detectL(x, y)\n",
    "        #         detectU(x, y)\n",
    "        #     else:\n",
    "        #         detectR(x, y)\n",
    "        #         detectU(x, y)\n",
    "\n",
    "        # for i in range(n):\n",
    "        #     for j in range(m):\n",
    "\n",
    "        #         handler(i , j)\n",
    "\n",
    "        \n",
    "        # return ds.find(getId(0, 0)) == ds.find(getId(n - 1, m - 1))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class DisjoinSet:\n",
    "\n",
    "    def __init__(self, n):\n",
    "        self.f = list(range(n))\n",
    "\n",
    "    def find(self, x):\n",
    "        if x == self.f[x]:\n",
    "            return x\n",
    "        self.f[x] = self.find(self.f[x])\n",
    "        return self.f[x]\n",
    "    def merge(self, x, y):\n",
    "        self.f[self.find(x)] = self.find(y)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[int]]) -> bool:\n",
    "\n",
    "        n, m = len(grid), len(grid[0])\n",
    "        ds = DisjoinSet(n * m)\n",
    "        patterns = [0, 0b1010, 0b0101, 0b1100, 0b0110, 0b1001, 0b0011]\n",
    "        dirs = [(-1, 0), (0, 1), (1, 0), (0, -1)]\n",
    "        \n",
    "        def getId(x, y):\n",
    "            return x * m + y\n",
    "\n",
    "        def handler(x, y):\n",
    "\n",
    "            pattern = patterns[grid[x][y]]\n",
    "\n",
    "            for i, (dx, dy) in enumerate(dirs):\n",
    "                if (pattern & (1 << i)) > 0:\n",
    "                    sx, sy = x + dx, y + dy\n",
    "                    if 0 <= sx < n and 0 <= sy < m and (patterns[grid[sx][sy]] & (1 << (i + 2) % 4)) > 0:\n",
    "                        ds.merge(getId(x, y), getId(sx, sy))\n",
    "        \n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "\n",
    "                handler(i , j)\n",
    "        \n",
    "        return ds.find(getId(0, 0)) == ds.find(getId(n - 1, m - 1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    class DisjointSet:\n",
    "        def __init__(self, n):\n",
    "            self.f = list(range(n))\n",
    "        \n",
    "        def find(self, x):\n",
    "            if x == self.f[x]:\n",
    "                return x\n",
    "            self.f[x] = self.find(self.f[x])\n",
    "            return self.f[x]\n",
    "        \n",
    "        def merge(self, x, y):\n",
    "            self.f[self.find(x)] = self.find(y)\n",
    "\n",
    "    # 邻接关系建图\n",
    "    def hasValidPath(self, grid: List[List[int]]) -> bool:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        ds = Solution.DisjointSet(m * n)\n",
    "\n",
    "        def getId(x, y):\n",
    "            return x * n + y\n",
    "        \n",
    "        def detectL(x, y):\n",
    "            if y - 1 >= 0 and grid[x][y - 1] in [1, 4, 6]:\n",
    "                ds.merge(getId(x, y), getId(x, y - 1))\n",
    "        \n",
    "        def detectR(x, y):\n",
    "            if y + 1 < n and grid[x][y + 1] in [1, 3, 5]:\n",
    "                ds.merge(getId(x, y), getId(x, y + 1))\n",
    "        \n",
    "        def detectU(x, y):\n",
    "            if x - 1 >= 0 and grid[x - 1][y] in [2, 3, 4]:\n",
    "                ds.merge(getId(x, y), getId(x - 1, y))\n",
    "        \n",
    "        def detectD(x, y):\n",
    "            if x + 1 < m and grid[x + 1][y] in [2, 5, 6]:\n",
    "                ds.merge(getId(x, y), getId(x + 1, y))\n",
    "\n",
    "        def handler(x, y):\n",
    "            if grid[x][y] == 1:\n",
    "                detectL(x, y)\n",
    "                detectR(x, y)\n",
    "            elif grid[x][y] == 2:\n",
    "                detectU(x, y)\n",
    "                detectD(x, y)\n",
    "            elif grid[x][y] == 3:\n",
    "                detectL(x, y)\n",
    "                detectD(x, y)\n",
    "            elif grid[x][y] == 4:\n",
    "                detectR(x, y)\n",
    "                detectD(x, y)\n",
    "            elif grid[x][y] == 5:\n",
    "                detectL(x, y)\n",
    "                detectU(x, y)\n",
    "            else:\n",
    "                detectR(x, y)\n",
    "                detectU(x, y)\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                handler(i, j)\n",
    "        \n",
    "        return ds.find(getId(0, 0)) == ds.find(getId(m - 1, n - 1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    class DisjoinSet():\n",
    "        def __init__(self, n):\n",
    "            self.f = list(range(n))\n",
    "\n",
    "        def find(self, x):\n",
    "            if x == self.f[x]:\n",
    "                return x\n",
    "            self.f[x] = self.find(self.f[x])\n",
    "            return self.f[x]\n",
    "\n",
    "        def merge(self, x, y):\n",
    "            self.f[self.find(x)] = self.find(y)\n",
    "\n",
    "    def hasValidPath(self, grid: List[List[int]]) -> bool:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        ds = Solution.DisjoinSet(m*n)\n",
    "        \n",
    "        def getId(x, y):\n",
    "            return x * n + y\n",
    "        \n",
    "        def detectL(x, y):\n",
    "            if y - 1 >= 0 and grid[x][y - 1] in [1, 4, 6]:\n",
    "                ds.merge(getId(x, y), getId(x, y - 1))\n",
    "        \n",
    "        def detectR(x, y):\n",
    "            if y + 1 < n and grid[x][y + 1] in [1, 3, 5]:\n",
    "                ds.merge(getId(x, y), getId(x, y + 1))\n",
    "        \n",
    "        def detectU(x, y):\n",
    "            if x - 1 >= 0 and grid[x - 1][y] in [2, 3, 4]:\n",
    "                ds.merge(getId(x, y), getId(x - 1, y))\n",
    "        \n",
    "        def detectD(x, y):\n",
    "            if x + 1 < m and grid[x + 1][y] in [2, 5, 6]:\n",
    "                ds.merge(getId(x, y), getId(x + 1, y))\n",
    "\n",
    "        def handler(x, y):\n",
    "            if grid[x][y] == 1:\n",
    "                detectL(x, y)\n",
    "                detectR(x, y)\n",
    "            elif grid[x][y] == 2:\n",
    "                detectU(x, y)\n",
    "                detectD(x, y)\n",
    "            elif grid[x][y] == 3:\n",
    "                detectL(x, y)\n",
    "                detectD(x, y)\n",
    "            elif grid[x][y] == 4:\n",
    "                detectR(x, y)\n",
    "                detectD(x, y)\n",
    "            elif grid[x][y] == 5:\n",
    "                detectL(x, y)\n",
    "                detectU(x, y)\n",
    "            else:\n",
    "                detectR(x, y)\n",
    "                detectU(x, y)\n",
    "        for j in range(n):\n",
    "            for i in range(m):\n",
    "                handler(i, j)\n",
    "        \n",
    "        return ds.find(getId(0, 0)) == ds.find(getId(m - 1, n - 1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    class DisjointSet:\n",
    "        def __init__(self, n):\n",
    "            self.f = list(range(n))\n",
    "        \n",
    "        def find(self, x):\n",
    "            if x == self.f[x]:\n",
    "                return x\n",
    "            self.f[x] = self.find(self.f[x])\n",
    "            return self.f[x]\n",
    "        \n",
    "        def merge(self, x, y):\n",
    "            self.f[self.find(x)] = self.find(y)\n",
    "\n",
    "    def hasValidPath(self, grid: List[List[int]]) -> bool:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        ds = Solution.DisjointSet(m * n)\n",
    "\n",
    "        def getId(x, y):\n",
    "            return x * n + y\n",
    "        \n",
    "        def detectL(x, y):\n",
    "            if y - 1 >= 0 and grid[x][y - 1] in [1, 4, 6]:\n",
    "                ds.merge(getId(x, y), getId(x, y - 1))\n",
    "        \n",
    "        def detectR(x, y):\n",
    "            if y + 1 < n and grid[x][y + 1] in [1, 3, 5]:\n",
    "                ds.merge(getId(x, y), getId(x, y + 1))\n",
    "        \n",
    "        def detectU(x, y):\n",
    "            if x - 1 >= 0 and grid[x - 1][y] in [2, 3, 4]:\n",
    "                ds.merge(getId(x, y), getId(x - 1, y))\n",
    "        \n",
    "        def detectD(x, y):\n",
    "            if x + 1 < m and grid[x + 1][y] in [2, 5, 6]:\n",
    "                ds.merge(getId(x, y), getId(x + 1, y))\n",
    "\n",
    "        def handler(x, y):\n",
    "            if grid[x][y] == 1:\n",
    "                detectL(x, y)\n",
    "                detectR(x, y)\n",
    "            elif grid[x][y] == 2:\n",
    "                detectU(x, y)\n",
    "                detectD(x, y)\n",
    "            elif grid[x][y] == 3:\n",
    "                detectL(x, y)\n",
    "                detectD(x, y)\n",
    "            elif grid[x][y] == 4:\n",
    "                detectR(x, y)\n",
    "                detectD(x, y)\n",
    "            elif grid[x][y] == 5:\n",
    "                detectL(x, y)\n",
    "                detectU(x, y)\n",
    "            else:\n",
    "                detectR(x, y)\n",
    "                detectU(x, y)\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                handler(i, j)\n",
    "        \n",
    "        return ds.find(getId(0, 0)) == ds.find(getId(m - 1, n - 1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    class DisjointSet:\n",
    "        def __init__(self, n):\n",
    "            self.f = list(range(n))\n",
    "        \n",
    "        def find(self, x):\n",
    "            if x == self.f[x]:\n",
    "                return x\n",
    "            self.f[x] = self.find(self.f[x])\n",
    "            return self.f[x]\n",
    "        \n",
    "        def merge(self, x, y):\n",
    "            self.f[self.find(x)] = self.find(y)\n",
    "\n",
    "    def hasValidPath(self, grid: List[List[int]]) -> bool:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        ds = Solution.DisjointSet(m * n)\n",
    "\n",
    "        def getId(x, y):\n",
    "            return x * n + y\n",
    "        \n",
    "        def detectL(x, y):\n",
    "            if y - 1 >= 0 and grid[x][y - 1] in [1, 4, 6]:\n",
    "                ds.merge(getId(x, y), getId(x, y - 1))\n",
    "        \n",
    "        def detectR(x, y):\n",
    "            if y + 1 < n and grid[x][y + 1] in [1, 3, 5]:\n",
    "                ds.merge(getId(x, y), getId(x, y + 1))\n",
    "        \n",
    "        def detectU(x, y):\n",
    "            if x - 1 >= 0 and grid[x - 1][y] in [2, 3, 4]:\n",
    "                ds.merge(getId(x, y), getId(x - 1, y))\n",
    "        \n",
    "        def detectD(x, y):\n",
    "            if x + 1 < m and grid[x + 1][y] in [2, 5, 6]:\n",
    "                ds.merge(getId(x, y), getId(x + 1, y))\n",
    "\n",
    "        def handler(x, y):\n",
    "            if grid[x][y] == 1:\n",
    "                detectL(x, y)\n",
    "                detectR(x, y)\n",
    "            elif grid[x][y] == 2:\n",
    "                detectU(x, y)\n",
    "                detectD(x, y)\n",
    "            elif grid[x][y] == 3:\n",
    "                detectL(x, y)\n",
    "                detectD(x, y)\n",
    "            elif grid[x][y] == 4:\n",
    "                detectR(x, y)\n",
    "                detectD(x, y)\n",
    "            elif grid[x][y] == 5:\n",
    "                detectL(x, y)\n",
    "                detectU(x, y)\n",
    "            else:\n",
    "                detectR(x, y)\n",
    "                detectU(x, y)\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                handler(i, j)\n",
    "        \n",
    "        return ds.find(getId(0, 0)) == ds.find(getId(m - 1, n - 1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    class DisjointSet:\n",
    "        def __init__(self, n):\n",
    "            self.f = list(range(n))\n",
    "        \n",
    "        def find(self, x):\n",
    "            if x == self.f[x]:\n",
    "                return x\n",
    "            self.f[x] = self.find(self.f[x])\n",
    "            return self.f[x]\n",
    "        \n",
    "        def merge(self, x, y):\n",
    "            self.f[self.find(x)] = self.find(y)\n",
    "\n",
    "    def hasValidPath(self, grid: List[List[int]]) -> bool:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        ds = Solution.DisjointSet(m * n)\n",
    "\n",
    "        def getId(x, y):\n",
    "            return x * n + y\n",
    "        \n",
    "        def detectL(x, y):\n",
    "            if y - 1 >= 0 and grid[x][y - 1] in [1, 4, 6]:\n",
    "                ds.merge(getId(x, y), getId(x, y - 1))\n",
    "        \n",
    "        def detectR(x, y):\n",
    "            if y + 1 < n and grid[x][y + 1] in [1, 3, 5]:\n",
    "                ds.merge(getId(x, y), getId(x, y + 1))\n",
    "        \n",
    "        def detectU(x, y):\n",
    "            if x - 1 >= 0 and grid[x - 1][y] in [2, 3, 4]:\n",
    "                ds.merge(getId(x, y), getId(x - 1, y))\n",
    "        \n",
    "        def detectD(x, y):\n",
    "            if x + 1 < m and grid[x + 1][y] in [2, 5, 6]:\n",
    "                ds.merge(getId(x, y), getId(x + 1, y))\n",
    "\n",
    "        def handler(x, y):\n",
    "            if grid[x][y] == 1:\n",
    "                detectL(x, y)\n",
    "                detectR(x, y)\n",
    "            elif grid[x][y] == 2:\n",
    "                detectU(x, y)\n",
    "                detectD(x, y)\n",
    "            elif grid[x][y] == 3:\n",
    "                detectL(x, y)\n",
    "                detectD(x, y)\n",
    "            elif grid[x][y] == 4:\n",
    "                detectR(x, y)\n",
    "                detectD(x, y)\n",
    "            elif grid[x][y] == 5:\n",
    "                detectL(x, y)\n",
    "                detectU(x, y)\n",
    "            else:\n",
    "                detectR(x, y)\n",
    "                detectU(x, y)\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                handler(i, j)\n",
    "        \n",
    "        return ds.find(getId(0, 0)) == ds.find(getId(m - 1, n - 1))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class DisjoinSet:\n",
    "\n",
    "    def __init__(self, n):\n",
    "        self.f = list(range(n))\n",
    "\n",
    "    def find(self, x):\n",
    "        if x == self.f[x]:\n",
    "            return x\n",
    "        self.f[x] = self.find(self.f[x])\n",
    "        return self.f[x]\n",
    "    def merge(self, x, y):\n",
    "        self.f[self.find(x)] = self.find(y)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[int]]) -> bool:\n",
    "\n",
    "        n, m = len(grid), len(grid[0])\n",
    "        ds = DisjoinSet(n * m)\n",
    "\n",
    "        def getId(x, y):\n",
    "            return x * m + y\n",
    "\n",
    "        def detectL(x, y):\n",
    "            if 0 <= x < n and 0 <= y - 1 < m and grid[x][y - 1] in set([1, 4, 6]):\n",
    "                ds.merge(getId(x, y), getId(x, y - 1))\n",
    "        def detectR(x, y):\n",
    "            if 0 <= x < n and 0 <= y + 1 < m and grid[x][y + 1] in set([1, 3, 5]):\n",
    "                ds.merge(getId(x, y), getId(x, y + 1))\n",
    "\n",
    "        def detectU(x, y):\n",
    "            if 0 <= x - 1 < n and 0 <= y < m and grid[x - 1][y] in set([2, 3, 4]):\n",
    "                ds.merge(getId(x, y), getId(x - 1, y ))\n",
    "\n",
    "        def detectD(x, y):\n",
    "            if 0 <= x + 1 < n and 0 <= y < m and grid[x + 1][y] in set([2, 5, 6]):\n",
    "                ds.merge(getId(x, y), getId(x + 1, y ))\n",
    "\n",
    "        def handler(x, y):\n",
    "            if grid[x][y] == 1:\n",
    "                detectL(x, y)\n",
    "                detectR(x, y)\n",
    "            elif grid[x][y] == 2:\n",
    "                detectU(x, y)\n",
    "                detectD(x, y)\n",
    "            elif grid[x][y] == 3:\n",
    "                detectL(x, y)\n",
    "                detectD(x, y)\n",
    "            elif grid[x][y] == 4:\n",
    "                detectR(x, y)\n",
    "                detectD(x, y)\n",
    "            elif grid[x][y] == 5:\n",
    "                detectL(x, y)\n",
    "                detectU(x, y)\n",
    "            else:\n",
    "                detectR(x, y)\n",
    "                detectU(x, y)\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "\n",
    "                handler(i , j)\n",
    "\n",
    "        \n",
    "        return ds.find(getId(0, 0)) == ds.find(getId(n - 1, m - 1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class DisjoinSet:\n",
    "\n",
    "    def __init__(self, n):\n",
    "        self.f = list(range(n))\n",
    "\n",
    "    def find(self, x):\n",
    "        if x == self.f[x]:\n",
    "            return x\n",
    "        self.f[x] = self.find(self.f[x])\n",
    "        return self.f[x]\n",
    "    def merge(self, x, y):\n",
    "        self.f[self.find(x)] = self.find(y)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[int]]) -> bool:\n",
    "\n",
    "        n, m = len(grid), len(grid[0])\n",
    "        ds = DisjoinSet(n * m)\n",
    "\n",
    "        def getId(x, y):\n",
    "            return x * m + y\n",
    "\n",
    "        def detectL(x, y):\n",
    "            if 0 <= x < n and 0 <= y - 1 < m and grid[x][y - 1] in set([1, 4, 6]):\n",
    "                ds.merge(getId(x, y), getId(x, y - 1))\n",
    "        def detectR(x, y):\n",
    "            if 0 <= x < n and 0 <= y + 1 < m and grid[x][y + 1] in set([1, 3, 5]):\n",
    "                ds.merge(getId(x, y), getId(x, y + 1))\n",
    "\n",
    "        def detectU(x, y):\n",
    "            if 0 <= x - 1 < n and 0 <= y < m and grid[x - 1][y] in set([2, 3, 4]):\n",
    "                ds.merge(getId(x, y), getId(x - 1, y ))\n",
    "\n",
    "        def detectD(x, y):\n",
    "            if 0 <= x + 1 < n and 0 <= y < m and grid[x + 1][y] in set([2, 5, 6]):\n",
    "                ds.merge(getId(x, y), getId(x + 1, y ))\n",
    "\n",
    "        def handler(x, y):\n",
    "            if grid[x][y] == 1:\n",
    "                detectL(x, y)\n",
    "                detectR(x, y)\n",
    "            elif grid[x][y] == 2:\n",
    "                detectU(x, y)\n",
    "                detectD(x, y)\n",
    "            elif grid[x][y] == 3:\n",
    "                detectL(x, y)\n",
    "                detectD(x, y)\n",
    "            elif grid[x][y] == 4:\n",
    "                detectR(x, y)\n",
    "                detectD(x, y)\n",
    "            elif grid[x][y] == 5:\n",
    "                detectL(x, y)\n",
    "                detectU(x, y)\n",
    "            else:\n",
    "                detectR(x, y)\n",
    "                detectU(x, y)\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "\n",
    "                handler(i , j)\n",
    "\n",
    "        \n",
    "        return ds.find(getId(0, 0)) == ds.find(getId(n - 1, m - 1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[int]]) -> bool:\n",
    "        # 题意是什么意思，给你一张图，让你判断图中（0，0）到（m-1,n-1）是否连通\n",
    "        # 1：1，3，5     2：2，5，6        3：2，5，6      4：2，5，6      5，1，6\n",
    "        # 并查集\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        fa = list(range(m*n))\n",
    "        def find(x):\n",
    "            if x == fa[x]:\n",
    "                return x\n",
    "            fa[x] = find(fa[x])\n",
    "            return fa[x]\n",
    "        def merge(x,y):\n",
    "            fa[find(x)] = find(y)\n",
    "        # 连通\n",
    "        def getId(x,y):\n",
    "            return x*n+y\n",
    "        def detectL(x,y):\n",
    "            if y-1>= 0 and grid[x][y-1] in [1,4,6]:\n",
    "                merge(getId(x,y),getId(x,y-1))\n",
    "        def detectR(x,y):\n",
    "            if y+1 < n and grid[x][y+1] in [1,3,5]:\n",
    "                merge(getId(x,y),getId(x,y+1))\n",
    "        def detectU(x,y):\n",
    "            if x-1>= 0 and grid[x-1][y] in [2,4,3]:\n",
    "                merge(getId(x,y),getId(x-1,y))\n",
    "        def detectD(x,y):\n",
    "            if x+1 < m and grid[x+1][y] in [2,5,6]:\n",
    "                merge(getId(x,y),getId(x+1,y))\n",
    "        def handler(x,y):\n",
    "            if grid[x][y] == 1:\n",
    "                detectL(x,y)\n",
    "                detectR(x,y)\n",
    "            if grid[x][y] == 2:\n",
    "                detectU(x,y)\n",
    "                detectD(x,y)\n",
    "            if grid[x][y] == 3:\n",
    "                detectL(x,y)\n",
    "                detectD(x,y)\n",
    "            if grid[x][y] == 4:\n",
    "                detectD(x,y)\n",
    "                detectR(x,y)\n",
    "            if grid[x][y] == 5:\n",
    "                detectU(x,y)\n",
    "                detectL(x,y)\n",
    "            if grid[x][y] == 6:\n",
    "                detectU(x,y)\n",
    "                detectR(x,y)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                handler(i,j)\n",
    "        return find(getId(0,0)) == find(getId(m-1,n-1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[int]]) -> bool:\n",
    "        # 题意是什么意思，给你一张图，让你判断图中（0，0）到（m-1,n-1）是否连通\n",
    "        # 1：1，3，5     2：2，5，6        3：2，5，6      4：2，5，6      5，1，6\n",
    "        # 并查集\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        fa = list(range(m*n))\n",
    "        def find(x):\n",
    "        # 找x的根节点\n",
    "            if x != fa[x]:\n",
    "                fa[x] = find(fa[x])\n",
    "            return fa[x]\n",
    "        def merge(x,y):\n",
    "            fa[find(x)] = find(y)\n",
    "        # 连通\n",
    "        def getId(x,y):\n",
    "            return x*n+y\n",
    "        def detectL(x,y):\n",
    "            if y-1>= 0 and grid[x][y-1] in [1,4,6]:\n",
    "                merge(getId(x,y),getId(x,y-1))\n",
    "        def detectR(x,y):\n",
    "            if y+1 < n and grid[x][y+1] in [1,3,5]:\n",
    "                merge(getId(x,y),getId(x,y+1))\n",
    "        def detectU(x,y):\n",
    "            if x-1>= 0 and grid[x-1][y] in [2,4,3]:\n",
    "                merge(getId(x,y),getId(x-1,y))\n",
    "        def detectD(x,y):\n",
    "            if x+1 < m and grid[x+1][y] in [2,5,6]:\n",
    "                merge(getId(x,y),getId(x+1,y))\n",
    "        def handler(x,y):\n",
    "            if grid[x][y] == 1:\n",
    "                detectL(x,y)\n",
    "                detectR(x,y)\n",
    "            if grid[x][y] == 2:\n",
    "                detectU(x,y)\n",
    "                detectD(x,y)\n",
    "            if grid[x][y] == 3:\n",
    "                detectL(x,y)\n",
    "                detectD(x,y)\n",
    "            if grid[x][y] == 4:\n",
    "                detectD(x,y)\n",
    "                detectR(x,y)\n",
    "            if grid[x][y] == 5:\n",
    "                detectU(x,y)\n",
    "                detectL(x,y)\n",
    "            if grid[x][y] == 6:\n",
    "                detectU(x,y)\n",
    "                detectR(x,y)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                handler(i,j)\n",
    "        return find(getId(0,0)) == find(getId(m-1,n-1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[int]]) -> bool:\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        fa = list(range(m*n))\n",
    "        # 并查集\n",
    "        def find(x):\n",
    "            if fa[x] != x:\n",
    "                fa[x] = find(fa[x])\n",
    "            return fa[x]\n",
    "        def merge(x,y):\n",
    "            fa[find(x)] = find(y)\n",
    "        def get_id(x,y):\n",
    "            return x*n+y\n",
    "        # 连通\n",
    "        def link_l(x,y):\n",
    "            if 0 <= y-1 and grid[x][y-1] in [1,4,6]:\n",
    "                merge(get_id(x,y),get_id(x,y-1))\n",
    "        def link_r(x,y):\n",
    "            if y+1<n and grid[x][y+1] in [1,3,5]:\n",
    "                merge(get_id(x,y),get_id(x,y+1))\n",
    "        def link_u(x,y):\n",
    "            if 0 <= x-1 and grid[x-1][y] in [2,3,4]:\n",
    "                merge(get_id(x,y),get_id(x-1,y))\n",
    "        def link_d(x,y):\n",
    "            if x+1<m and grid[x+1][y] in [2,5,6]:\n",
    "                merge(get_id(x,y),get_id(x+1,y))\n",
    "        def link(x,y):\n",
    "            if grid[x][y] == 1:\n",
    "                link_l(x,y)\n",
    "                link_r(x,y)\n",
    "            if grid[x][y] == 2:\n",
    "                link_u(x,y)\n",
    "                link_d(x,y)\n",
    "            if grid[x][y] == 3:\n",
    "                link_l(x,y)\n",
    "                link_d(x,y)\n",
    "            if grid[x][y] == 4:\n",
    "                link_d(x,y)\n",
    "                link_r(x,y)\n",
    "            if grid[x][y] == 5:\n",
    "                link_l(x,y)\n",
    "                link_u(x,y)\n",
    "            if grid[x][y] == 6:\n",
    "                link_u(x,y)\n",
    "                link_r(x,y)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                link(i,j)\n",
    "        return find(get_id(0,0)) == find(get_id(m-1,n-1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distanceLimitedPathsExist(self, n: int, edgeList: List[List[int]], queries: List[List[int]]) -> List[bool]:\n",
    "        edgeList.sort(key=lambda e: e[2])\n",
    "\n",
    "        # 并查集模板\n",
    "        fa = list(range(n))\n",
    "        def find(x: int) -> int:\n",
    "            if fa[x] != x:\n",
    "                fa[x] = find(fa[x])\n",
    "            return fa[x]\n",
    "        def merge(from_: int, to: int) -> None:\n",
    "            fa[find(from_)] = find(to)\n",
    "\n",
    "        ans, k = [False] * len(queries), 0\n",
    "        # 查询的下标按照 limit 从小到大排序，方便离线\n",
    "        for i, (p, q, limit) in sorted(enumerate(queries), key=lambda p: p[1][2]):\n",
    "            while k < len(edgeList) and edgeList[k][2] < limit:\n",
    "                merge(edgeList[k][0], edgeList[k][1])\n",
    "                k += 1\n",
    "            ans[i] = find(p) == find(q)\n",
    "        return ans\n",
    "\n",
    "# 作者：力扣官方题解\n",
    "# 链接：https://leetcode.cn/problems/checking-existence-of-edge-length-limited-paths/solutions/2018397/jian-cha-bian-chang-du-xian-zhi-de-lu-ji-cdr5/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n):\n",
    "        self.parent = list(range(n))\n",
    "        \n",
    "    def find(self, u):\n",
    "        if self.parent[u] == u:\n",
    "            return u\n",
    "        self.parent[u] = self.find(self.parent[u])\n",
    "        return self.parent[u]\n",
    "    \n",
    "    def merge(self, u, v):\n",
    "        u = self.find(u)\n",
    "        v = self.find(v)\n",
    "        if u == v:\n",
    "            return\n",
    "        self.parent[u] = v\n",
    "        \n",
    "class Solution:\n",
    "    def distanceLimitedPathsExist(self, n: int, edgeList: List[List[int]], queries: List[List[int]]) -> List[bool]:\n",
    "        edgeList.sort(key=lambda x: x[2])\n",
    "        queries = sorted(enumerate(queries), key=lambda x: x[1][2])\n",
    "        \n",
    "        uf = UnionFind(n)\n",
    "        answer = [False] * len(queries)\n",
    "        edge_idx = 0\n",
    "        \n",
    "        for i, (p, q, limit) in queries:\n",
    "            while edge_idx < len(edgeList) and edgeList[edge_idx][2] < limit:\n",
    "                uf.merge(edgeList[edge_idx][0], edgeList[edge_idx][1])\n",
    "                edge_idx += 1\n",
    "            \n",
    "            answer[i] = (uf.find(p) == uf.find(q))\n",
    "        \n",
    "        return answer\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "def merge(r1, r2, target, k):\n",
    "    tmp = [(abs(n - target), n) for n in r1 + r2]\n",
    "    tmp.sort()\n",
    "    return [n[1] for n in tmp[:k]]\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def closestKValues(self, root: Optional[TreeNode], target: float, k: int) -> List[int]:\n",
    "        results = []\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return \n",
    "\n",
    "            dfs(root.left)\n",
    "            dfs(root.right)\n",
    "            \n",
    "            item = (-abs(root.val - target), root.val)\n",
    "            if len(results) < k:\n",
    "                heapq.heappush(results, item)\n",
    "            else:\n",
    "                heapq.heappushpop(results, item)\n",
    "        dfs(root)\n",
    "        return [r[1] for r in results]\n",
    "        \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestNumber(self, cost: List[int], target: int) -> str:\n",
    "        dp=['0']*(target+1)\n",
    "        cost_map={c:i+1 for i,c in enumerate(cost)}\n",
    "        #print('cost',cost_map)\n",
    "        def merge(s,bit):\n",
    "            if s=='0':\n",
    "                return '0'\n",
    "            for i in range(len(s)):\n",
    "                ch=s[i]\n",
    "                if int(ch)<=bit:\n",
    "                    return s[:i]+str(bit)+s[i:]\n",
    "            return s+str(bit)\n",
    "        for i in range(1,target+1):\n",
    "            for c,bit in cost_map.items():\n",
    "                tmp=''\n",
    "                if i-c==0:\n",
    "                    tmp=str(bit)\n",
    "                elif i-c>0:\n",
    "                    tmp=merge(dp[i-c],bit)\n",
    "                if len(tmp)>len(dp[i]):\n",
    "                    dp[i]=tmp\n",
    "                elif len(tmp)==len(dp[i]):\n",
    "                    buf=[tmp,dp[i]]\n",
    "                    buf.sort()\n",
    "                    dp[i]=buf[1]\n",
    "        return dp[-1]\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestNumber(self, cost: List[int], target: int) -> str:\n",
    "        dp=['0']*(target+1)\n",
    "        cost_map={c:i+1 for i,c in enumerate(cost)}\n",
    "        def merge(s,bit):\n",
    "            if s=='0':\n",
    "                return '0'\n",
    "            for i in range(len(s)):\n",
    "                ch=s[i]\n",
    "                if int(ch)<=bit:\n",
    "                    return s[:i]+str(bit)+s[i:]\n",
    "            return s+str(bit)\n",
    "        for i in range(1,target+1):\n",
    "            for c,bit in cost_map.items():\n",
    "                tmp=''\n",
    "                if i-c==0:\n",
    "                    tmp=str(bit)\n",
    "                elif i-c>0:\n",
    "                    tmp=merge(dp[i-c],bit)\n",
    "                if len(tmp)>len(dp[i]):\n",
    "                    dp[i]=tmp\n",
    "                elif len(tmp)==len(dp[i]):\n",
    "                    buf=[tmp,dp[i]]\n",
    "                    buf.sort()\n",
    "                    dp[i]=buf[1]\n",
    "        return dp[-1]\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n) -> None:\n",
    "        self.components = n\n",
    "        self.fa = list(range(n))\n",
    "        self.rank = [1] * n\n",
    "\n",
    "    def __str__(self) -> str:\n",
    "        return \" \".join(map(str, self.fa))\n",
    "\n",
    "    def find(self, x):\n",
    "        if self.fa[x] != x:\n",
    "            self.fa[x] = self.find(self.fa[x])\n",
    "        return self.fa[x]\n",
    "\n",
    "    def union(self, x, y):\n",
    "        fx, fy = self.find(x), self.find(y)\n",
    "        if fx == fy:\n",
    "            return False\n",
    "        if self.rank[fy] > self.rank[fx]:\n",
    "            fx, fy = fy, fx\n",
    "        self.fa[fy] = fx\n",
    "        self.rank[fx] += self.rank[fy]\n",
    "        self.components -= 1\n",
    "        return True\n",
    "\n",
    "    def is_connected(self, x, y):\n",
    "        return self.find(x) == self.find(y)\n",
    "\n",
    "    def all_is_connected(self):\n",
    "        return self.components == 1\n",
    "\n",
    "    def size(self, x):\n",
    "        return self.rank[self.find(x)]\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def gcdSort(self, nums: List[int]) -> bool:\n",
    "        N = max(nums) + 1\n",
    "        uf = UnionFind(N)\n",
    "\n",
    "        for x in nums:\n",
    "            i = 2\n",
    "            y = x\n",
    "            # merge x to it's primes\n",
    "            while i * i <= x:\n",
    "                if x % i == 0:\n",
    "                    uf.union(y, i)\n",
    "                    while x % i == 0:\n",
    "                        x //= i\n",
    "                i += 1\n",
    "            if x > 1:\n",
    "                uf.union(y, x)\n",
    "\n",
    "        for x, y in zip(nums, sorted(nums)):\n",
    "            # print(x, y, uf)\n",
    "            if not uf.is_connected(x, y):\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\r\n",
    "# class TreeNode:\r\n",
    "#     def __init__(self, val=0, left=None, right=None):\r\n",
    "#         self.val = val\r\n",
    "#         self.left = left\r\n",
    "#         self.right = right\r\n",
    "def checkBST(root: TreeNode) -> tuple[bool, int, int]:\r\n",
    "    if root.left is None and root.right is None:\r\n",
    "        return True, root.val, root.val\r\n",
    "    if root.left is None:\r\n",
    "        rightBST, rightMin, rightMax = checkBST(root.right)\r\n",
    "        return rightBST and root.val < rightMin, root.val, rightMax\r\n",
    "    if root.right is None:\r\n",
    "        leftBST, leftMin, leftMax = checkBST(root.left)\r\n",
    "        return leftBST and root.val > leftMax, leftMin, root.val\r\n",
    "\r\n",
    "    leftBST, leftMin, leftMax = checkBST(root.left)\r\n",
    "    rightBST, rightMin, rightMax = checkBST(root.right)\r\n",
    "    return leftBST and rightBST and leftMax < root.val < rightMin, leftMin, rightMax\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def canMerge(self, trees: List[TreeNode]) -> Optional[TreeNode]:\r\n",
    "        # find leaves\r\n",
    "        m = 50001\r\n",
    "        n = 0\r\n",
    "        leaves: dict[int, tuple[int, int]] = dict()\r\n",
    "        for i, node in enumerate(trees):\r\n",
    "            _, l, r = checkBST(node)\r\n",
    "            m = min(m, l)\r\n",
    "            n = max(n, r)\r\n",
    "            # node with no children is not considered as leaf\r\n",
    "            # because no roots having same val, therefore no other tree can merge to it\r\n",
    "            if node.left is not None:\r\n",
    "                if node.left.val in leaves:\r\n",
    "                    return None\r\n",
    "                leaves[node.left.val] = (i, 0)\r\n",
    "            if node.right is not None:\r\n",
    "                if node.right.val in leaves:\r\n",
    "                    return None\r\n",
    "                leaves[node.right.val] = (i, 1)\r\n",
    "        \r\n",
    "        # find root\r\n",
    "        root = None\r\n",
    "        for node in trees:\r\n",
    "            # all roots needs to match with one leaf, except one as final root\r\n",
    "            if node.val not in leaves:\r\n",
    "                if root is not None:\r\n",
    "                    return None\r\n",
    "                root = node\r\n",
    "        \r\n",
    "        if root is None:\r\n",
    "            root = trees[0]\r\n",
    "\r\n",
    "        # build tree\r\n",
    "        for node in trees:\r\n",
    "            if node is not root:\r\n",
    "                if leaves[node.val][1] == 0:\r\n",
    "                    trees[leaves[node.val][0]].left = node\r\n",
    "                else:\r\n",
    "                    trees[leaves[node.val][0]].right = node\r\n",
    "\r\n",
    "        b, l, r = checkBST(root)\r\n",
    "        return root if b and l == m and r == n else None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def canMerge(self, trees: List[TreeNode]) -> Optional[TreeNode]:\n",
    "        n = len(trees)\n",
    "        if n == 1:\n",
    "            return trees[0]\n",
    "\n",
    "        l = [1] * n\n",
    "        vals = defaultdict(set)\n",
    "        for i,t in enumerate(trees):\n",
    "            for j,x in enumerate([t.left, t.right], start=1):\n",
    "                if x:\n",
    "                    l[i] += 1\n",
    "                    vals[x.val].add((i,j))\n",
    "                if l[i] > 1:\n",
    "                    vals[t.val].add((i,0))\n",
    "        # check single nodes\n",
    "        for i in range(n):\n",
    "            if l[i] == 1 and trees[i].val not in vals:\n",
    "                return\n",
    "        \n",
    "        # merge\n",
    "        isRoot = [v > 1 for v in l]\n",
    "        for v,z in vals.items():\n",
    "            if len(z) == 1:\n",
    "                continue\n",
    "            if len(z) >= 3:\n",
    "                return\n",
    "            z = sorted(z, key=lambda a: a[-1])\n",
    "            i, a = z[0]\n",
    "            j, b = z[1]\n",
    "            if not (0 == a < b):\n",
    "                return\n",
    "            if b == 1:\n",
    "                trees[j].left = trees[i]\n",
    "            else:\n",
    "                trees[j].right = trees[i]\n",
    "            isRoot[i] = False\n",
    "\n",
    "        if sum(isRoot) != 1:\n",
    "            return\n",
    "        root = trees[isRoot.index(True)]\n",
    "        \n",
    "        seen = set()\n",
    "        def isBST(x, l, r):\n",
    "            if not x:\n",
    "                return True\n",
    "            if not (l < x.val < r):\n",
    "                return False\n",
    "            if not isBST(x.left, l, x.val):\n",
    "                return False\n",
    "            if not isBST(x.right, x.val, r):\n",
    "                return False\n",
    "            seen.add(x.val)\n",
    "            return True\n",
    "        \n",
    "        if not isBST(root, -math.inf, math.inf):\n",
    "            return\n",
    "        if len(seen) != len(vals):\n",
    "            return\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def canMerge(self, trees: List[TreeNode]) -> Optional[TreeNode]:\n",
    "        n = len(trees)\n",
    "        if n == 1:\n",
    "            return trees[0]\n",
    "\n",
    "        l = [1] * n\n",
    "        vals = defaultdict(set)\n",
    "        for i,t in enumerate(trees):\n",
    "            for j,x in enumerate([t.left, t.right], start=1):\n",
    "                if x:\n",
    "                    l[i] += 1\n",
    "                    vals[x.val].add((i,j))\n",
    "                if l[i] > 1:\n",
    "                    vals[t.val].add((i,0))\n",
    "        # check single nodes\n",
    "        for i in range(n):\n",
    "            if l[i] == 1 and trees[i].val not in vals:\n",
    "                return\n",
    "        \n",
    "        # merge\n",
    "        isRoot = [v > 1 for v in l]\n",
    "        for v,z in vals.items():\n",
    "            print(v, [x for x in z])\n",
    "            if len(z) == 1:\n",
    "                continue\n",
    "            if len(z) >= 3:\n",
    "                return\n",
    "            z = sorted(z, key=lambda a: a[-1])\n",
    "            i, a = z[0]\n",
    "            j, b = z[1]\n",
    "            if not (0 == a < b):\n",
    "                return\n",
    "            if b == 1:\n",
    "                trees[j].left = trees[i]\n",
    "            else:\n",
    "                trees[j].right = trees[i]\n",
    "            isRoot[i] = False\n",
    "\n",
    "        if sum(isRoot) != 1:\n",
    "            return\n",
    "        root = trees[isRoot.index(True)]\n",
    "        \n",
    "        seen = set()\n",
    "        def isBST(x, l, r):\n",
    "            if not x:\n",
    "                return True\n",
    "            if not (l < x.val < r):\n",
    "                return False\n",
    "            if not isBST(x.left, l, x.val):\n",
    "                return False\n",
    "            if not isBST(x.right, x.val, r):\n",
    "                return False\n",
    "            seen.add(x.val)\n",
    "            return True\n",
    "        # prev = -math.inf\n",
    "        # def isBST(x):\n",
    "        #     nonlocal prev\n",
    "        #     if x.left and isBST(x.left) == False:\n",
    "        #         return False\n",
    "        #     if prev >= x.val:\n",
    "        #         return False\n",
    "        #     prev = x.val\n",
    "        #     if x.right and isBST(x.right) == False:\n",
    "        #         return False\n",
    "        #     return True\n",
    "        \n",
    "        if not isBST(root, -math.inf, math.inf):\n",
    "            return\n",
    "        if len(seen) != len(vals):\n",
    "            return\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:\n",
    "        tmp = list2\n",
    "        b_end = tmp\n",
    "        while tmp!=None:\n",
    "            if tmp.next!=None:\n",
    "                b_end = tmp.next\n",
    "            tmp = tmp.next\n",
    "        index = 0\n",
    "        res = None\n",
    "        if a == 0:\n",
    "            res = list2\n",
    "        else:\n",
    "            res = list1\n",
    "        tmp = list1\n",
    "        while tmp!=None:\n",
    "            if index+1 == a:\n",
    "                k = tmp.next\n",
    "                tmp.next = list2\n",
    "                tmp = k\n",
    "                index += 1 \n",
    "                continue\n",
    "            if index == b:\n",
    "                b_end.next = tmp.next\n",
    "            tmp = tmp.next\n",
    "            index += 1\n",
    "        return res\n",
    "            \n",
    "            \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:\n",
    "        start = ListNode(0)\n",
    "        t0 = start\n",
    "        start.next = list1\n",
    "        #实例1： 先找到2（t0）\n",
    "        save_a = a\n",
    "        while(a):\n",
    "            t0 = t0.next\n",
    "            a -= 1\n",
    "        #print(t0.val)\n",
    "        t1 = t0\n",
    "        b = b - save_a + 2\n",
    "        #print(b)\n",
    "        while(b):\n",
    "            t1 = t1.next\n",
    "            b -= 1\n",
    "        #print(t1.val)\n",
    "        #插入\n",
    "        t0.next = list2\n",
    "        #list2的最后一个\n",
    "        while(list2.next):\n",
    "            list2 = list2.next\n",
    "        list2.next = t1 \n",
    "        return start.next\n",
    "\n",
    "        \n",
    "        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:\n",
    "        fast, slow = list1, list1\n",
    "        k = b - a + 1\n",
    "        for _ in range(k):\n",
    "            fast = fast.next\n",
    "        for _ in range(a-1):\n",
    "            slow = slow.next\n",
    "            fast = fast.next\n",
    "        end = fast.next\n",
    "        pre, rear = list2, list2\n",
    "        while rear.next:\n",
    "            rear = rear.next\n",
    "        slow.next = pre\n",
    "        rear.next = end\n",
    "        return list1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:\n",
    "        pre = dummy = ListNode(-1)\n",
    "        pre.next = list1\n",
    "        prea  = pre\n",
    "        for i in range(a):\n",
    "            prea = prea.next\n",
    "        nodeb = list1    \n",
    "        for i in range(b):\n",
    "            nodeb = nodeb.next\n",
    "        prea.next = list2    \n",
    "        cur = list2\n",
    "        while cur.next:\n",
    "            cur = cur.next\n",
    "        cur.next = nodeb.next    \n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:\n",
    "        l = list1\n",
    "        for _ in range(a - 1):\n",
    "            l = l.next\n",
    "        r = l.next\n",
    "        for _ in range(b - a + 1):\n",
    "            r = r.next\n",
    "        l.next = list2\n",
    "        tail = list2\n",
    "        while tail.next: tail = tail.next\n",
    "        tail.next = r\n",
    "        \n",
    "        return list1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:\n",
    "        prea = dummy = ListNode(0)\n",
    "        dummy.next = list1\n",
    "        nxb = None\n",
    "        b -= a\n",
    "        while a:\n",
    "            prea = prea.next\n",
    "            a -= 1\n",
    "        nxb = prea.next\n",
    "        while b:\n",
    "            nxb = nxb.next\n",
    "            b -= 1\n",
    "        nxb = nxb.next\n",
    "\n",
    "        head = list2\n",
    "        while head and head.next:\n",
    "            head = head.next\n",
    "\n",
    "        prea.next = list2\n",
    "        head.next = nxb\n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:\n",
    "        head = ListNode(0)\n",
    "        curr = head\n",
    "        i = 0\n",
    "        while i < a:\n",
    "            i += 1\n",
    "            curr.next = list1\n",
    "            list1 = list1.next\n",
    "            curr = curr.next\n",
    "        while i < b:\n",
    "            i += 1\n",
    "            list1 = list1.next\n",
    "        curr.next = list2\n",
    "        while curr.next:\n",
    "            curr = curr.next\n",
    "        curr.next = list1.next\n",
    "        return head.next\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:\n",
    "        hashmap1 = dict()\n",
    "        i = 0\n",
    "        node1 = list1\n",
    "        while node1:\n",
    "            hashmap1[i] = node1\n",
    "            i += 1\n",
    "            node1 = node1.next\n",
    "        hashmap1[a-1].next = list2\n",
    "        node2 = list2\n",
    "        while node2.next:\n",
    "            node2 = node2.next\n",
    "        node2.next = hashmap1.get(b+1, None)\n",
    "        hashmap1[b].next = None\n",
    "        return hashmap1[0]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:\n",
    "        endnote = list1\n",
    "        count = -1\n",
    "        while endnote:\n",
    "            count += 1\n",
    "            if count == b:\n",
    "                endnote = endnote.next\n",
    "                break\n",
    "            endnote = endnote.next\n",
    "\n",
    "        cur2 = list2\n",
    "        while cur2:\n",
    "            if cur2.next == None:\n",
    "                cur2.next = endnote\n",
    "                break\n",
    "            cur2 = cur2.next\n",
    "\n",
    "        cur = list1\n",
    "        count = 0\n",
    "        while cur:\n",
    "            count += 1\n",
    "            if count == a:\n",
    "                cur.next = list2\n",
    "                break\n",
    "            cur = cur.next\n",
    "        return list1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:\n",
    "        \n",
    "        \n",
    "        \n",
    "        # my solution ... 432 ms ... 19.6 MB ... \n",
    "        #  time: O(n+m)\n",
    "        # space: O(n)\n",
    "        \n",
    "        idx2nod = {}\n",
    "        node = list1\n",
    "        index = 0\n",
    "        while node:\n",
    "            idx2nod[index] = node\n",
    "            index += 1\n",
    "            node = node.next\n",
    "        node = list2\n",
    "        while node.next:\n",
    "            node = node.next\n",
    "        idx2nod[a-1].next = list2\n",
    "        node.next = idx2nod[b+1]\n",
    "        return list1\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:\n",
    "        aa = []\n",
    "        tmp = list1\n",
    "        while tmp is not None:\n",
    "            aa.append(tmp.val)\n",
    "            tmp = tmp.next\n",
    "        def make(a):\n",
    "            ret = ListNode()\n",
    "            now = ret\n",
    "            for x in a:\n",
    "                tmp = ListNode(x)\n",
    "                now.next = tmp\n",
    "                now = tmp\n",
    "            return ret.next, now\n",
    "        a1,t1 = make(aa[:a])\n",
    "        a2,_ = make(aa[b+1:])\n",
    "        t1.next = list2\n",
    "        head = list2\n",
    "        while head.next is not None:\n",
    "            head = head.next\n",
    "        head.next=a2\n",
    "        return a1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:\n",
    "        ans = ListNode(0)\n",
    "        ans.next = list1\n",
    "        q = list2\n",
    "        while list2 and list2.next:\n",
    "            list2 = list2.next\n",
    "        count = 0\n",
    "        p = list1\n",
    "        while p:\n",
    "            count += 1\n",
    "            if count == a:\n",
    "                pre = p\n",
    "            p = p.next\n",
    "            if count == b+1:\n",
    "                break\n",
    "        pre.next = q\n",
    "        list2.next = p\n",
    "        return ans.next\n",
    "\n",
    "        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:\n",
    "        # dummy = ListNode(0)\n",
    "        # dummy.next = list1\n",
    "        # temp = dummy\n",
    "        temp = list1\n",
    "        for i in range(a-1):\n",
    "            temp = temp.next\n",
    "        prev = temp\n",
    "               \n",
    "        for j in range(b-a+2):\n",
    "            temp = temp.next\n",
    "        last = temp\n",
    "\n",
    "        cur = list2\n",
    "        while cur.next:\n",
    "            cur = cur.next\n",
    "        prev.next = list2\n",
    "        cur.next = last\n",
    "\n",
    "        return list1\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:\n",
    "        node = list1\n",
    "        length = 0\n",
    "        while list1:\n",
    "            if length == a - 1:\n",
    "                pre = list1\n",
    "            if length == b + 1:\n",
    "                nex = list1\n",
    "            length += 1\n",
    "            list1 = list1.next\n",
    "        pre.next = list2\n",
    "        while list2.next:\n",
    "            list2 = list2.next\n",
    "        list2.next = nex\n",
    "        return node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:\n",
    "        dummy = ListNode(-1)\n",
    "        dummy.next = list1\n",
    "        slow = fast = dummy\n",
    "        for _ in range(b-a+1):\n",
    "            fast = fast.next\n",
    "        for _ in range(a):\n",
    "            slow = slow.next\n",
    "            fast = fast.next\n",
    "        \n",
    "        tail_list2 = list2\n",
    "        while tail_list2.next:\n",
    "            tail_list2 = tail_list2.next\n",
    "\n",
    "        slow.next = list2\n",
    "        tail_list2.next = fast.next\n",
    "        fast.next = None\n",
    "\n",
    "        return dummy.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:\n",
    "        cur1 = list1\n",
    "        cur2 = list2\n",
    "        prev = prev1 = ListNode()\n",
    "        \n",
    "        n = 0\n",
    "        while cur1:\n",
    "            if n < a:\n",
    "                prev1.next = cur1\n",
    "                prev1 = prev1.next\n",
    "                cur1 = cur1.next\n",
    "           \n",
    "            elif a <= n < b:\n",
    "                cur1 = cur1.next\n",
    "            elif n == b:\n",
    "                cur1 = cur1.next\n",
    "                while cur2:\n",
    "                   prev1.next = cur2\n",
    "                   prev1 = prev1.next\n",
    "                   cur2 = cur2.next\n",
    "      \n",
    "            elif n > a:\n",
    "\n",
    "                prev1.next = cur1\n",
    "                prev1 = prev1.next\n",
    "                cur1 = cur1.next\n",
    "            n = n + 1\n",
    "        return prev.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:\n",
    "        # 连接list2尾部和b+1个节点\n",
    "        L1 = list1\n",
    "        L2 = list2\n",
    "        while L2.next:\n",
    "            L2 = L2.next\n",
    "        while b >= 0:\n",
    "            L1 = L1.next\n",
    "            b -= 1\n",
    "        L2.next = L1\n",
    "\n",
    "        # 连接list2头部\n",
    "        # 这里用哑结点更方便一点\n",
    "        L1 = ListNode(-1, list1)\n",
    "        while a > 0:\n",
    "            L1 = L1.next\n",
    "            a -= 1\n",
    "        L1.next = list2\n",
    "        return list1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:\n",
    "        if not list1:\n",
    "            return list1\n",
    "        dummy = ListNode(0)\n",
    "        dummy.next = list1\n",
    "        # 找到a-1节点\n",
    "        nodeA = list1\n",
    "        for i in range(a-1):\n",
    "            nodeA = nodeA.next\n",
    "        # 找到b+1节点\n",
    "        nodeB = nodeA\n",
    "        for i in range(a-1, b+1):\n",
    "            nodeB = nodeB.next\n",
    "\n",
    "        # 找到list2的尾节点\n",
    "        tail = list2\n",
    "        while tail.next:\n",
    "            tail = tail.next\n",
    "        # 把list2接入到list1的a，b位置\n",
    "        tail.next = nodeB\n",
    "        nodeA.next = list2\n",
    "\n",
    "        return dummy.next\n",
    "            \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:\n",
    "        point = res = ListNode(0)\n",
    "        res.next = list1\n",
    "        res = res.next\n",
    "        for i in range(a-1):\n",
    "            list1 = list1.next\n",
    "        tmp = list1.next\n",
    "        for i in range(b-a):\n",
    "            tmp = tmp.next\n",
    "        list1.next = list2\n",
    "        while list1.next:\n",
    "            list1 = list1.next\n",
    "        list1.next = tmp.next\n",
    "        return point.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:\n",
    "        pA = list1\n",
    "        for i in range(a-1):\n",
    "            pA = pA.next\n",
    "        pB = pA\n",
    "        for i in range(b-a+1):\n",
    "            pB = pB.next\n",
    "        pA.next = list2\n",
    "        p = list2\n",
    "        while p.next:\n",
    "            p = p.next\n",
    "        p.next = pB.next\n",
    "        return list1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:\n",
    "        dummy = ListNode(-1, list1)\n",
    "        curA = dummy\n",
    "        tmp = list1\n",
    "        # 找到b, 标记b+1\n",
    "        for _ in range(b):\n",
    "            tmp = tmp.next\n",
    "        curB = tmp.next\n",
    "        tmp.next = None\n",
    "\n",
    "        # 找到a, 标记a-1\n",
    "        for _ in range(a):\n",
    "            curA = curA.next\n",
    "        curA.next = None\n",
    "\n",
    "        # 遍历list2, 标记尾节点tail\n",
    "        cur = list2\n",
    "        while cur.next:\n",
    "            cur = cur.next\n",
    "        \n",
    "        # 整合链表\n",
    "        curA.next = list2\n",
    "        cur.next = curB\n",
    "        return dummy.next\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:\n",
    "        p1, p2 = list1, list1\n",
    "        while a > 1:\n",
    "            p1 = p1.next\n",
    "            a -= 1\n",
    "        while b > -1:\n",
    "            p2 = p2.next\n",
    "            b -= 1\n",
    "        \n",
    "        tail = list2\n",
    "        while tail.next:\n",
    "            tail = tail.next\n",
    "\n",
    "        p1.next = list2\n",
    "        tail.next = p2\n",
    "\n",
    "        return list1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:\n",
    "        \"\"\"\n",
    "          因为a>=1,所以不会删除第一个节点\n",
    "        \"\"\"\n",
    "        node_num = 0\n",
    "        cur = list1\n",
    "        while cur and node_num<a-1:\n",
    "            cur = cur.next\n",
    "            node_num += 1\n",
    "        cur1 = cur\n",
    "        while cur1 and node_num<=b:\n",
    "            cur1 = cur1.next\n",
    "            node_num += 1\n",
    "        cur.next = list2\n",
    "        while cur.next:\n",
    "            cur = cur.next\n",
    "        cur.next = cur1\n",
    "        return list1\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:\n",
    "        ind = 0\n",
    "        p = list1\n",
    "        while p:\n",
    "            if ind == a-1:start = p\n",
    "            if ind == b+1:end = p\n",
    "            p = p.next\n",
    "            ind = ind+1\n",
    "        start.next = list2\n",
    "        while list2.next:\n",
    "            list2 = list2.next\n",
    "        list2.next = end\n",
    "        return list1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:\n",
    "        offseta = a\n",
    "        offsetb = b\n",
    "        offset = max(a, b)\n",
    "        a = b = None\n",
    "\n",
    "        a_pre = None\n",
    "        cur = list1\n",
    "        offseti = 0\n",
    "        while cur and offseti <= offset:\n",
    "            if offseti == offseta-1:\n",
    "                a_pre = cur\n",
    "            if offseti == offsetb:\n",
    "                b = cur\n",
    "\n",
    "            offseti += 1\n",
    "            cur = cur.next\n",
    "\n",
    "        tail2 = list2\n",
    "        while tail2 and tail2.next:\n",
    "            tail2 = tail2.next\n",
    "\n",
    "        if not a_pre and not b:\n",
    "            return list2\n",
    "\n",
    "        if not a_pre and b:\n",
    "            if tail2:\n",
    "                tail2.next = b.next\n",
    "            if not list2:\n",
    "                return b.next\n",
    "            return list2\n",
    "\n",
    "        if a_pre and not b:\n",
    "            a_pre.next = None\n",
    "            a_pre.next = list2\n",
    "            return list1\n",
    "\n",
    "        if a_pre and b:\n",
    "            if not list2:\n",
    "                a_pre.next = b.next\n",
    "            else:\n",
    "                a_pre.next = list2\n",
    "                tail2.next = b.next\n",
    "            return list1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:\n",
    "        node = list1\n",
    "        for _ in range(a-1):\n",
    "            node = node.next\n",
    "        part3_node = node\n",
    "        for _ in range(b-a+2):\n",
    "            part3_node = part3_node.next\n",
    "        node2 = list2\n",
    "        while node2.next:\n",
    "            node2 = node2.next\n",
    "        node.next = list2\n",
    "        node2.next = part3_node\n",
    "        return list1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:\n",
    "        dummy = ListNode(-1, list1)\n",
    "        curr = dummy\n",
    "        start = 0\n",
    "        while list1:\n",
    "            if start == a:\n",
    "                while list2:\n",
    "                    curr.next = list2\n",
    "                    list2 = list2.next\n",
    "                    curr = curr.next\n",
    "            while start >= a and start <= b:\n",
    "                list1 = list1.next\n",
    "                start += 1\n",
    "            start += 1\n",
    "            curr.next = list1\n",
    "            curr = curr.next\n",
    "            list1 = list1.next\n",
    "        return dummy.next\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:\n",
    "        p=q=list1\n",
    "        for _ in range(a-1):\n",
    "            p=p.next\n",
    "        for _ in range(b):\n",
    "            q=q.next\n",
    "        p.next=list2\n",
    "        while p.next:\n",
    "            p=p.next\n",
    "        p.next=q.next\n",
    "        q.next=None\n",
    "        return list1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:\n",
    "        cur_node = list1\n",
    "        c = 0\n",
    "        while cur_node:\n",
    "            if c == a - 1:\n",
    "                st_node = cur_node\n",
    "            if c == b + 1:\n",
    "                ed_node = cur_node\n",
    "            cur_node = cur_node.next\n",
    "            c += 1\n",
    "        \n",
    "        cur_node = list1\n",
    "        while cur_node:\n",
    "            if cur_node == st_node:\n",
    "                cur_node.next = list2\n",
    "                while list2.next:\n",
    "                    list2 = list2.next\n",
    "                list2.next = ed_node\n",
    "                cur_node = ed_node\n",
    "            cur_node = cur_node.next\n",
    "        \n",
    "        return list1\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # dummy_node = ListNode()\n",
    "        # dummy_node.next = list1\n",
    "        # while \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:\n",
    "        p=q=list1\n",
    "        for _ in range(a-1):p=p.next#遍历到a\n",
    "        for _ in range(b):q=q.next#找到b+1\n",
    "        p.next=list2\n",
    "        while p.next:\n",
    "            p=p.next\n",
    "        p.next=q.next\n",
    "        q.next=None\n",
    "        return list1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:\n",
    "        p=q=list1\n",
    "        for _ in range(a-1):p=p.next#遍历到a-1节点\n",
    "        for _ in range(b):q=q.next#找到b\n",
    "        p.next=list2 #a-1指向Liste2\n",
    "        while p.next:\n",
    "            p=p.next #遍历到末尾\n",
    "        p.next=q.next\n",
    "        q.next=None\n",
    "        return list1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:\n",
    "        p,q = list1,list1\n",
    "        for i in range(a-1):\n",
    "            p = p.next\n",
    "        for i in range(b):\n",
    "            q = q.next\n",
    "        p.next = list2\n",
    "        while p.next:\n",
    "            p = p.next\n",
    "        p.next = q.next\n",
    "        q.next = None\n",
    "        return list1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:\n",
    "        # 需要寻找a的前缀和b的next\n",
    "        protect = list1\n",
    "        list1_index = 1\n",
    "        while list1.next:\n",
    "            if list1_index == a:\n",
    "                # 记录下来a节点的前缀位置\n",
    "                flag_a_prior = list1\n",
    "            if list1_index == b:\n",
    "                # 记录下来b节点的next位置\n",
    "                flag_b_next = list1.next.next\n",
    "            list1 = list1.next\n",
    "            list1_index += 1\n",
    "        # 把list2拼接在a的前缀的next\n",
    "        flag_a_prior.next = list2\n",
    "        # 找到list2的尾指针\n",
    "        while list2.next:\n",
    "            list2 = list2.next\n",
    "        # 把b的next拼接在list2尾指针的位置\n",
    "        list2.next = flag_b_next\n",
    "        return protect\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:\n",
    "        cur=list1\n",
    "        for i in range(a-1):\n",
    "            cur=cur.next\n",
    "        aft=list1\n",
    "        for i in range(b):\n",
    "            aft=aft.next\n",
    "        cur.next=list2\n",
    "        while cur.next:\n",
    "            cur=cur.next\n",
    "        cur.next=aft.next\n",
    "        aft.next=None\n",
    "        return list1\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:\n",
    "        preA = list1\n",
    "        for _ in range(a - 1):\n",
    "            preA = preA.next\n",
    "        preB = preA\n",
    "        for _ in range(b - a + 2):\n",
    "            preB = preB.next\n",
    "        preA.next = list2\n",
    "        while list2.next:\n",
    "            list2 = list2.next\n",
    "        list2.next = preB\n",
    "        return list1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:\n",
    "        p,q = list1,list1\n",
    "        for i in range(a-1):\n",
    "            p = p.next\n",
    "        for i in range(b):\n",
    "            q = q.next\n",
    "        p.next = list2\n",
    "        while p.next:\n",
    "            p = p.next\n",
    "        p.next = q.next\n",
    "        q.next = None\n",
    "        return list1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:\n",
    "        site=0\n",
    "        site2=0\n",
    "        len2=0\n",
    "        cur1=list1\n",
    "        cur2=list2\n",
    "        while cur2:\n",
    "            len2+=1\n",
    "            cur2=cur2.next\n",
    "        while cur1:\n",
    "            site2+=1\n",
    "            cur1=cur1.next\n",
    "            if site2==b:\n",
    "                end=cur1.next\n",
    "                break\n",
    "        cur1=list1\n",
    "        while cur1:\n",
    "            site+=1\n",
    "            if site==a:\n",
    "                cur1.next=list2\n",
    "                while cur1.next:\n",
    "                    cur1=cur1.next\n",
    "                    site+=1\n",
    "                cur1.next=end\n",
    "                break\n",
    "            cur1=cur1.next\n",
    "        return list1\n",
    "\n",
    "    \n",
    "\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:\n",
    "        def find(h, pos):\n",
    "            now = h\n",
    "            if pos == -1:\n",
    "                while now.next:\n",
    "                    now = now.next\n",
    "            else:\n",
    "                for i in range(pos):\n",
    "                    now = now.next\n",
    "            return now\n",
    "\n",
    "        pre = find(list1, a - 1)\n",
    "        tail = find(list1, b + 1)\n",
    "        pre.next =  list2\n",
    "        find(list2, -1).next = tail\n",
    "        return list1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:\n",
    "\n",
    "        # 获取索引为a-1的节点\n",
    "        aprev = list1\n",
    "        for _ in range(a-1):\n",
    "            aprev = aprev.next\n",
    "        \n",
    "        # 获取索引为b+1的节点\n",
    "        bnext = aprev\n",
    "        for _ in range(b-a+2):\n",
    "            bnext = bnext.next\n",
    "\n",
    "        # 合并\n",
    "        aprev.next = list2\n",
    "        while aprev.next:\n",
    "            aprev = aprev.next\n",
    "        aprev.next = bnext\n",
    "\n",
    "        return list1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:\n",
    "        cur=list1\n",
    "        i=0\n",
    "        while cur:\n",
    "            if i==a-1:\n",
    "                node1=cur\n",
    "            elif i==b:\n",
    "                node2=cur\n",
    "                break\n",
    "            i+=1\n",
    "            cur=cur.next\n",
    "        node1.next=list2\n",
    "        while list2.next:\n",
    "            list2=list2.next\n",
    "        list2.next=node2.next\n",
    "        node2.next=None\n",
    "        return list1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:\n",
    "        cur = 0\n",
    "        left = list1\n",
    "        pre = None\n",
    "        while cur!=a:\n",
    "            pre = left\n",
    "            left = left.next\n",
    "            cur+=1\n",
    "        right = left\n",
    "        while cur!=b:\n",
    "            right = right.next\n",
    "            cur+=1\n",
    "        ans = None\n",
    "        cur = list2\n",
    "        while cur.next is not None:\n",
    "            cur = cur.next\n",
    "        cur.next = right.next\n",
    "        if pre is None:\n",
    "            ans = list2\n",
    "        else:\n",
    "            ans = list1\n",
    "            pre.next = list2\n",
    "            cur = list2\n",
    "        return ans\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:\n",
    "        p = q = list1\n",
    "        for _ in range(a-1):\n",
    "            p = p.next\n",
    "        for _ in range(b):\n",
    "            q = q.next\n",
    "        p.next = list2\n",
    "        while p.next:\n",
    "            p = p.next\n",
    "        p.next = q.next\n",
    "        q.next = None\n",
    "        return list1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:\n",
    "        index = 0\n",
    "        pivot = list1\n",
    "        while index < a-1:\n",
    "            pivot = pivot.next\n",
    "            index += 1\n",
    "        left = pivot\n",
    "        while index <= b:\n",
    "            pivot = pivot.next\n",
    "            index +=1\n",
    "        right = pivot\n",
    "        left.next = list2\n",
    "        pivot = list2\n",
    "        while pivot.next!=None:\n",
    "            pivot = pivot.next\n",
    "        pivot.next = right\n",
    "        return list1\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:\n",
    "        lenth = 0\n",
    "        cur = list1\n",
    "        before_a = after_b = list1\n",
    "        for _ in range(a-1):\n",
    "            before_a = before_a.next\n",
    "        \n",
    "        for _ in range(b+1):\n",
    "            after_b = after_b.next\n",
    "        \n",
    "        before_a.next = list2\n",
    "        while before_a.next:\n",
    "            before_a = before_a.next\n",
    "        before_a.next = after_b\n",
    "\n",
    "        return list1\n",
    "        \n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:\n",
    "        p = q = list1\n",
    "        for _ in range(a - 1):\n",
    "            p = p.next\n",
    "        for _ in range(b):\n",
    "            q = q.next\n",
    "        # print(p.val,q.val)\n",
    "        p.next = list2\n",
    "        while p.next:\n",
    "            p = p.next\n",
    "        p.next = q.next\n",
    "        # print(list1)\n",
    "        # q.next = None\n",
    "        return list1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:\n",
    "        lenth = 0\n",
    "        cur = cur_a = cur_b = list1\n",
    "        before_a = after_b = list1\n",
    "        while cur:\n",
    "            lenth += 1\n",
    "            if lenth == a:\n",
    "                before_a = cur\n",
    "            if lenth == b+1:\n",
    "                after_b = cur.next\n",
    "                cur.next = None\n",
    "                before_a.next = None\n",
    "                break\n",
    "            cur = cur.next\n",
    "\n",
    "        # list2的结尾\n",
    "        cur = list2\n",
    "        while cur.next:\n",
    "            cur = cur.next\n",
    "        before_a.next, cur.next = list2, after_b\n",
    "\n",
    "        return list1\n",
    "        \n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:\n",
    "        cache1 = []\n",
    "        cache2 = []\n",
    "        while list1:\n",
    "            cache1.append(list1)\n",
    "            list1 = list1.next\n",
    "        while list2:\n",
    "            cache2.append(list2)\n",
    "            list2 = list2.next\n",
    "        cache2[-1].next = cache1[b+1] if b+1<len(cache1) else None\n",
    "        if a-1>=0:\n",
    "            cache1[a-1].next = cache2[0]\n",
    "            return cache1[0]\n",
    "        else:\n",
    "            return cache2[0]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:\n",
    "        ans = ListNode(0, list1)\n",
    "        temp = ans\n",
    "        flag = 0\n",
    "        while flag < a:\n",
    "            flag += 1\n",
    "            temp = temp.next\n",
    "        temp2 = temp\n",
    "        while flag <= b:\n",
    "            temp2 = temp2.next\n",
    "            flag += 1\n",
    "        temp.next = list2\n",
    "        while temp.next:\n",
    "            temp = temp.next\n",
    "        temp.next = temp2.next\n",
    "        return ans.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:\n",
    "        head = list1 \n",
    "        for _ in range(1, a):\n",
    "            list1 = list1.next \n",
    "        start = list1 \n",
    "        for _ in range(a, b+2):\n",
    "            list1 = list1.next\n",
    "        end = list1 \n",
    "        start.next = list2\n",
    "        while list2.next:\n",
    "            list2 = list2.next \n",
    "        list2.next = end\n",
    "        return head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:\n",
    "        node = list1\n",
    "        for _ in range(a - 1):\n",
    "            node = node.next\n",
    "        middle = node.next.next\n",
    "        node.next = list2\n",
    "\n",
    "        # 找到切断后右边最左的节点\n",
    "        for _ in range(b - a):\n",
    "            middle = middle.next\n",
    "        \n",
    "\n",
    "        # 找到list2的尾部\n",
    "        list2 = list2\n",
    "        while list2.next:\n",
    "            list2 = list2.next\n",
    "        \n",
    "        list2.next = middle\n",
    "        return list1\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\r\n",
    "# class ListNode:\r\n",
    "#     def __init__(self, val=0, next=None):\r\n",
    "#         self.val = val\r\n",
    "#         self.next = next\r\n",
    "class Solution:\r\n",
    "    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:\r\n",
    "            \r\n",
    "            dummy = ListNode(0)\r\n",
    "            dummy.next = list1\r\n",
    "            pre = dummy\r\n",
    "            cur = list1\r\n",
    "            for _ in range(a):\r\n",
    "                pre = cur\r\n",
    "                cur = cur.next\r\n",
    "            pre.next = list2\r\n",
    "            while list2.next:\r\n",
    "                list2 = list2.next\r\n",
    "            for _ in range(b-a+1):\r\n",
    "                cur = cur.next\r\n",
    "            list2.next = cur\r\n",
    "            return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:\n",
    "        cur1=list1\n",
    "        i=0\n",
    "        while i<a-1:\n",
    "            cur1=cur1.next\n",
    "            i+=1\n",
    "        cur2=cur1.next\n",
    "        cur1.next=list2\n",
    "        while cur1.next!=None:\n",
    "            cur1=cur1.next\n",
    "\n",
    "        while i<b:\n",
    "            cur2=cur2.next\n",
    "            i+=1\n",
    "        cur1.next=cur2\n",
    "        return list1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:\n",
    "        dummy = p = q = ListNode(0, list1)\n",
    "        for i in range(a):\n",
    "            p = p.next\n",
    "        for i in range(b + 2):\n",
    "            q = q.next\n",
    "        p.next = list2\n",
    "        p = list2\n",
    "        while p.next != None:\n",
    "            p = p.next\n",
    "        p.next = q\n",
    "        return dummy.next\n",
    "\n",
    "        \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def merge(self, intervals: List[List[int]]) -> List[List[int]]:\n",
    "        intervals.sort()  # remember to sort!!!\n",
    "        res = []\n",
    "        for i in intervals:\n",
    "            if not res or res[-1][1] < i[0]:\n",
    "                res.append(i)\n",
    "            else:\n",
    "                res[-1][1] = max(res[-1][1], i[1])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for an interval.\n",
    "# class Interval:\n",
    "#     def __init__(self, s=0, e=0):\n",
    "#         self.start = s\n",
    "#         self.end = e\n",
    "\n",
    "class Solution:\n",
    "    def merge(self, intervals):\n",
    "        out = []\n",
    "        for i in sorted(intervals, key=lambda x:x.start):\n",
    "            if out and out[-1].end >= i.start:\n",
    "                out[-1].end = max(out[-1].end, i.end)\n",
    "            else:\n",
    "                out.append(i)\n",
    "        \n",
    "        return out\n",
    "        \"\"\"\n",
    "        :type intervals: List[Interval]\n",
    "        :rtype: List[Interval]\n",
    "        \"\"\"\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for an interval.\n",
    "# class Interval:\n",
    "#     def __init__(self, s=0, e=0):\n",
    "#         self.start = s\n",
    "#         self.end = e\n",
    "\n",
    "class Solution:\n",
    "    def merge(self, intervals):\n",
    "        \"\"\"\n",
    "        :type intervals: List[Interval]\n",
    "        :rtype: List[Interval]\n",
    "        \"\"\"\n",
    "        if len(intervals) == 0:\n",
    "            return []\n",
    "        intervals = sorted(intervals, key = lambda x:x.start)\n",
    "        res = [intervals[0]]\n",
    "        for node in intervals[1:]:\n",
    "            if node.start<=res[-1].end:\n",
    "                res[-1].end = max(node.end,res[-1].end)\n",
    "            else:\n",
    "                res.append(node)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for an interval.\n",
    "# class Interval:\n",
    "#     def __init__(self, s=0, e=0):\n",
    "#         self.start = s\n",
    "#         self.end = e\n",
    "\n",
    "class Solution:\n",
    "    def merge(self, intervals):\n",
    "        \"\"\"\n",
    "        :type intervals: List[Interval]\n",
    "        :rtype: List[Interval]\n",
    "        \"\"\"\n",
    "        if len(intervals) <= 1:\n",
    "            return intervals\n",
    "        intervals.sort(key=lambda x: x.start)\n",
    "        cur = intervals[0]\n",
    "        ans = []\n",
    "        for i in range(1, len(intervals)):\n",
    "            if cur.end < intervals[i].start:\n",
    "                # non-overlap\n",
    "                ans.append(cur)\n",
    "                cur = intervals[i]\n",
    "            else:\n",
    "                # overlap\n",
    "                cur.end = max(cur.end, intervals[i].end)\n",
    "        if not ans or ans[-1].end < cur.start:\n",
    "            ans.append(cur)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def merge(self, intervals):\n",
    "        \"\"\"\n",
    "        :type intervals: List[Interval]\n",
    "        :rtype: List[Interval]\n",
    "        \"\"\"\n",
    "        ans = []\n",
    "        # self.quicksort(intervals, 0, len(intervals)-1)\n",
    "        intervals = sorted(intervals, key=lambda x: x.start)\n",
    "        for item in intervals:\n",
    "            if not ans or item.start > ans[-1].end:\n",
    "                ans.append(item)\n",
    "            elif item.end > ans[-1].end:\n",
    "                ans[-1].end = item.end\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for an interval.\n",
    "# class Interval:\n",
    "#     def __init__(self, s=0, e=0):\n",
    "#         self.start = s\n",
    "#         self.end = e\n",
    "\n",
    "class Solution:\n",
    "    def merge(self, intervals):\n",
    "        \"\"\"\n",
    "        :type intervals: List[Interval]\n",
    "        :rtype: List[Interval]\n",
    "        \"\"\"\n",
    "        res = []\n",
    "        if intervals:\n",
    "            i = 0\n",
    "            while intervals:\n",
    "                flag = False\n",
    "                start, end = intervals[0].start, intervals[0].end\n",
    "                j = 1\n",
    "                \n",
    "                while j < len(intervals):\n",
    "                    if (intervals[j].start >= start and intervals[j].start <= end) or (intervals[j].end >= start and intervals[j].end <= end) or (intervals[j].start <= start and intervals[j].end >= end):\n",
    "                        start = min(intervals[j].start, start)\n",
    "                        end = max(intervals[j].end, end)\n",
    "                        del intervals[j]\n",
    "                        intervals[0] = Interval(start, end)\n",
    "                        flag = True\n",
    "                        \n",
    "                    j += 1\n",
    "                    print(j)\n",
    "                if flag == False:\n",
    "                    del intervals[0]\n",
    "                    res.append([start, end])\n",
    "                print(start, end)\n",
    "                \n",
    "                #print(i, intervals)\n",
    "        return res\n",
    "                        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for an interval.\n",
    "# class Interval:\n",
    "#     def __init__(self, s=0, e=0):\n",
    "#         self.start = s\n",
    "#         self.end = e\n",
    "from itertools import chain\n",
    "class Solution:\n",
    "    def merge(self, intervals):\n",
    "        \"\"\"\n",
    "        :type intervals: List[Interval]\n",
    "        :rtype: List[Interval]\n",
    "        \"\"\"\n",
    "        ends = list(chain.from_iterable(((i.start, -1), (i.end, 1)) for i in intervals))\n",
    "        ends.sort();\n",
    "        dep = 0\n",
    "        result = []\n",
    "        for i, e in ends:\n",
    "            if dep == 0:\n",
    "                start = i\n",
    "            dep += e\n",
    "            if dep == 0:\n",
    "                result.append([start, i])\n",
    "        return result\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for an interval.\n",
    "# class Interval:\n",
    "#     def __init__(self, s=0, e=0):\n",
    "#         self.start = s\n",
    "#         self.end = e\n",
    "\n",
    "class Solution:\n",
    "    def merge(self, intervals: 'List[Interval]') -> 'List[Interval]':\n",
    "        _intervals = [[x.start, x.end] for x in intervals]\n",
    "        _intervals.sort(key=lambda x: (x[0], x[1]))\n",
    "\n",
    "        i = 1\n",
    "        while i < len(_intervals):\n",
    "            if _intervals[i][0] <= _intervals[i-1][1]:\n",
    "                _intervals[i-1][0] = min(_intervals[i][0], _intervals[i-1][0])\n",
    "                _intervals[i-1][1] = max(_intervals[i][1], _intervals[i-1][1])\n",
    "                del _intervals[i]\n",
    "            else:\n",
    "                i += 1\n",
    "\n",
    "        return _intervals\n",
    "            \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for an interval.\n",
    "# class Interval:\n",
    "#     def __init__(self, s=0, e=0):\n",
    "#         self.start = s\n",
    "#         self.end = e\n",
    "\n",
    "class Solution:\n",
    "    def merge(self, intervals):\n",
    "        \"\"\"\n",
    "        :type intervals: List[Interval]\n",
    "        :rtype: List[Interval]\n",
    "        \"\"\"\n",
    "        intervals = sorted(intervals, key = lambda x: x.start)\n",
    "        res = []\n",
    "        for ele in intervals:\n",
    "            if not res:\n",
    "                res.append(ele)\n",
    "            elif ele.start <= res[-1].end:\n",
    "                res[-1].end = max(ele.end, res[-1].end)\n",
    "            else:\n",
    "                res.append(ele)\n",
    "            print(\"ele: {}, {}\".format(ele.start, ele.end))\n",
    "            self.printEle(res)\n",
    "        return res\n",
    "    def printEle(self, intervals):\n",
    "        for i in intervals:\n",
    "            print(i.start, i.end, end = ',')\n",
    "        print('\\n')\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for an interval.\n",
    "# class Interval:\n",
    "#     def __init__(self, s=0, e=0):\n",
    "#         self.start = s\n",
    "#         self.end = e\n",
    "from operator import itemgetter\n",
    "class Solution:\n",
    "    def merge(self, _intervals):\n",
    "        \"\"\"\n",
    "        :type intervals: List[Interval]\n",
    "        :rtype: List[Interval]\n",
    "        \"\"\"\n",
    "        intervals = [[x.start,x.end] for x in _intervals]\n",
    "        if intervals == []:\n",
    "            return []\n",
    "        while True:\n",
    "            intervals.sort(key=itemgetter(0,1))\n",
    "            count = 0\n",
    "            for i in range(len(intervals)-1):\n",
    "                if intervals[i+1][0] <= intervals[i][1] <=intervals[i+1][1] or intervals[i][0] <=intervals[i+1][1] <= intervals[i][1]:\n",
    "                    intervals[i][0] = min(intervals[i][0],intervals[i+1][0])\n",
    "                    intervals[i][1] = max(intervals[i][1],intervals[i+1][1])\n",
    "                    intervals[i+1][0] = min(intervals[i][0], intervals[i + 1][0])\n",
    "                    intervals[i+1][1] = max(intervals[i][1], intervals[i + 1][1])\n",
    "                else:\n",
    "                    count+=1\n",
    "                    continue\n",
    "            if count == len(intervals)-1:\n",
    "                break\n",
    "            temp_l = list(set([str(i) for i in intervals]))\n",
    "            intervals = [eval((i)) for i in temp_l]\n",
    "        return intervals\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def merge(self, intervals):\n",
    "        if not intervals:\n",
    "            return []\n",
    "        intervals.sort()\n",
    "        res = []\n",
    "        cur = intervals[0]\n",
    "        for i in range(1, len(intervals)):\n",
    "            if intervals[i][0] <= cur[1]:\n",
    "                cur[1] = max(cur[1], intervals[i][1])\n",
    "            else:\n",
    "                res.append(cur)\n",
    "                cur = intervals[i]\n",
    "        res.append(cur)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def merge(self, intervals: List[List[int]]) -> List[List[int]]:\n",
    "        # sorted 区间list，便于后续遍历\n",
    "        intervals = sorted(intervals)\n",
    "        res = []\n",
    "        i = 0\n",
    "        # 对于每一个区间，我们首先判断它自己的最大值和后面一个区间的最小值哪个大\n",
    "        # 如果可以merge，那么还要判断两者的最大值哪个大，以确定merge后的区间上限\n",
    "        # 首先使用left和right来代表intervals的上下限\n",
    "        # 同时有一个指针指向自己，merge前的比较要保证指针合法\n",
    "        # merge后指针加一，同时由于指针指向的是自己，在无法merge后，还要再加以才能找到下一个起始区间\n",
    "        while i < len(intervals):\n",
    "            left = intervals[i][0]\n",
    "            right = intervals[i][1]\n",
    "            while i+1 < len(intervals) and right >= intervals[i+1][0]:\n",
    "                right = max(right,intervals[i+1][1])\n",
    "                i += 1\n",
    "            res.append([left,right])\n",
    "            i += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def merge(self, intervals: List[List[int]]) -> List[List[int]]:\n",
    "        res = []\n",
    "        intervals.sort(key=lambda x: x[0])\n",
    "        for i in intervals:\n",
    "            if res and i[0] <= res[-1][1]:\n",
    "                res[-1][1] = max(res[-1][1], i[1])\n",
    "            else:\n",
    "                #res.append(i)\n",
    "                res += i,\n",
    "        return res\n",
    "            \n",
    "        \n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def merge(self, intervals: List[List[int]]) -> List[List[int]]:\n",
    "        intervals.sort()\n",
    "        ans=[intervals[0]]\n",
    "        intervals=intervals[1:]\n",
    "        while len(intervals)>0:\n",
    "            if ans[-1][1]>=intervals[0][0] and ans[-1][1]<intervals[0][1]:\n",
    "                p=ans.pop()\n",
    "                ans.append([p[0],intervals[0][1]])\n",
    "                intervals=intervals[1:]\n",
    "            elif ans[-1][1]<intervals[0][0]:\n",
    "                ans.append(intervals[0])\n",
    "                intervals=intervals[1:]\n",
    "            else:\n",
    "                while len(intervals)>0 and ans[-1][1]>=intervals[0][1]:\n",
    "                    intervals=intervals[1:]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def merge(self, intervals: List[List[int]]) -> List[List[int]]:\n",
    "        intervals.sort()\n",
    "        n = len(intervals)\n",
    "        \n",
    "        ans = []\n",
    "        for interval in intervals:\n",
    "            if not ans:\n",
    "                ans.append(interval)\n",
    "            if ans[-1][1] >= interval[0]:\n",
    "                ans[-1][1] = max(ans[-1][1], interval[1])\n",
    "            else:\n",
    "                ans.append(interval)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def merge(self, intervals: List[List[int]]) -> List[List[int]]:\n",
    "        result = []\n",
    "        if not intervals:\n",
    "            return result\n",
    "        intervals = sorted(intervals)\n",
    "        for first, second in intervals:\n",
    "            if not result or result[-1][1] < first:\n",
    "                result.append([first, second])\n",
    "            else:\n",
    "                result[-1][1] = max(result[-1][1], second)\n",
    "        return result        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def merge(self, intervals):\n",
    "        intervals1 = sorted(intervals,key = lambda x:x[0])      #按照第一列排序（二位数组）##sorted(a, key=lambda x: (x[1], x[0]))  先按第二列排序，再按第一列排序\n",
    "        print(intervals1)\n",
    "        i = 0\n",
    "        while i < len(intervals1)-1:\n",
    "            print(i)\n",
    "            if intervals1[i][1] >= intervals1[i+1][0] and intervals1[i][1] < intervals1[i+1][1]:        #合并\n",
    "                intervals1[i][1] = intervals1[i+1][1]\n",
    "                del intervals1[i+1]\n",
    "                i -= 1    \n",
    "            elif intervals1[i][1] >= intervals1[i+1][0] and intervals1[i][1] > intervals1[i+1][1]:        #\n",
    "                del intervals1[i+1]\n",
    "                i -= 1\n",
    "            elif intervals1[i][1] == intervals1[i+1][1] and intervals1[i][0] >= intervals1[i+1][0]:\n",
    "                del intervals1[i]\n",
    "                i -=1\n",
    "            elif intervals1[i][1] == intervals1[i+1][1] and intervals1[i][0] < intervals1[i+1][0]:\n",
    "                del intervals1[i+1]\n",
    "                i -= 1\n",
    "            i += 1\n",
    "        return intervals1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def merge(self, intervals: List[List[int]]) -> List[List[int]]:\n",
    "        intervals.sort(key=itemgetter(0,1))\n",
    "        res = []\n",
    "        last_interval = intervals[0]\n",
    "        for i in range(1, len(intervals)):\n",
    "            cur_interval = intervals[i]\n",
    "            if cur_interval[0] <= last_interval[1]:\n",
    "                last_interval[1] = max(last_interval[1], cur_interval[1])\n",
    "            else:\n",
    "                res.append(last_interval)\n",
    "                last_interval = cur_interval\n",
    "\n",
    "        res.append(last_interval)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def merge(self, intervals: List[List[int]]) -> List[List[int]]:\n",
    "        intervals.sort()\n",
    "        ans = [intervals[0]]\n",
    "        L , R = 1 , 0\n",
    "        while L < len(intervals):\n",
    "            if ans[R][1] < intervals[L][0]:\n",
    "                ans.append(intervals[L])\n",
    "                R += 1\n",
    "                L += 1\n",
    "            else:\n",
    "                ans[R] = [ans[R][0],max(ans[R][1],intervals[L][1])]\n",
    "                L += 1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def merge(self, intervals: List[List[int]]) -> List[List[int]]:\n",
    "        n = len(intervals)\n",
    "        intervals.sort()\n",
    "        ans = [intervals[0]]\n",
    "        for i in range(1,n):\n",
    "            if intervals[i][0] <= ans[-1][1]:\n",
    "                ans[-1][1] = max(intervals[i][1],ans[-1][1])\n",
    "            else:\n",
    "                ans.append(intervals[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def merge(self, intervals: List[List[int]]) -> List[List[int]]:\n",
    "        merged = []\n",
    "        intervals.sort(key = lambda x : x[0])\n",
    "\n",
    "        for interval in intervals:\n",
    "            if not merged or merged[-1][1] < interval[0]:\n",
    "                merged.append(interval)\n",
    "            else:\n",
    "                merged[-1][1] = max(merged[-1][1], interval[1])\n",
    "        \n",
    "        return merged"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def merge(self, intervals: List[List[int]]) -> List[List[int]]:\n",
    "        intervals.sort(key=lambda x: x[0])\n",
    "\n",
    "        left, right = -1, -1\n",
    "        res = []\n",
    "\n",
    "        for x, y in intervals:\n",
    "            if x <= right and y > right:\n",
    "                res[-1][1] = y\n",
    "                right = y\n",
    "            elif x > right:\n",
    "                res.append([x, y])\n",
    "                left, right = x, y\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def merge(self, intervals: List[List[int]]) -> List[List[int]]:\n",
    "        res = []\n",
    "        intervals = sorted(intervals, key = lambda x:(x[0],x[1]))\n",
    "        # print(intervals)\n",
    "        left = intervals[0][0]\n",
    "        right = intervals[0][1]\n",
    "        for i in range(1,len(intervals)):\n",
    "            if right>= intervals[i][0]:\n",
    "                right = max(right,intervals[i][1])\n",
    "            else:\n",
    "                res.append([left,right])\n",
    "                left = intervals[i][0]\n",
    "                right = intervals[i][1]\n",
    "        res.append([left,right])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def merge(self, intervals: List[List[int]]) -> List[List[int]]:\n",
    "        intervals.sort(key = lambda x: (x[0], x[1]))\n",
    "        res = list()\n",
    "        s, t = intervals[0][0], intervals[0][1]\n",
    "        for i in range(len(intervals)):\n",
    "            new_s, new_t = intervals[i]\n",
    "            if new_s > t:\n",
    "                res += [[s, t]]\n",
    "                s, t = new_s, new_t\n",
    "            elif new_s <= t and new_t > t:\n",
    "                t = new_t\n",
    "            elif new_s <= t and new_t <= t:\n",
    "                continue\n",
    "        res += [[s, t]]\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def merge_intervals(ivts):\n",
    "    \"\"\"56\"\"\"\n",
    "    if len(ivts) == 1:\n",
    "        return ivts\n",
    "    ivts = sorted(ivts, key=lambda n: [n[0], n[1]])\n",
    "    res = []\n",
    "    prev = ivts[0]\n",
    "    for index in range(1, len(ivts)):\n",
    "        a, b = ivts[index]\n",
    "        pa, pb = prev\n",
    "        if a > pb:\n",
    "            res.append(prev)\n",
    "            prev = [a, b]\n",
    "        else:\n",
    "            prev = [pa, max(b, pb)]\n",
    "    res.append(prev)\n",
    "    return res\n",
    "\n",
    "class Solution:\n",
    "    def merge(self, intervals: List[List[int]]) -> List[List[int]]:\n",
    "        return merge_intervals(intervals)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def merge(self, intervals: List[List[int]]) -> List[List[int]]:\n",
    "        intervals.sort()\n",
    "        merged = []\n",
    "        for interval in intervals:\n",
    "            # 如果列表为空，或者当前区间与上一区间不重合，直接添加\n",
    "            if not merged or merged[-1][1] < interval[0]:\n",
    "                merged.append(interval)\n",
    "            else:\n",
    "                # 否则的话，我们就可以与上一区间进行合并\n",
    "                merged[-1][1] = max(merged[-1][1], interval[1])\n",
    "        return merged"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def merge(self, intervals: List[List[int]]) -> List[List[int]]:\n",
    "        intervals.sort(key = lambda x: x[0])\n",
    "        i = 0\n",
    "        while i < len(intervals) - 1:\n",
    "            if intervals[i][1] < intervals[i + 1][0]:\n",
    "                i += 1\n",
    "            else:\n",
    "                intervals[i][1] = max(intervals[i][1], intervals[i + 1][1])\n",
    "                intervals.pop(i + 1)\n",
    "        return intervals\n",
    "\n",
    "        # while i < len(intervals) - 1:\n",
    "        #     if intervals[i][1] >= intervals[i + 1][1]:\n",
    "        #         intervals.pop(i + 1)\n",
    "        #     elif intervals[i][1] >= intervals[i + 1][0]:\n",
    "        #         temp = [intervals[i][0], intervals[i + 1][1]]\n",
    "        #         intervals.pop(i)\n",
    "        #         intervals.pop(i)\n",
    "        #         intervals.insert(i, temp)\n",
    "        #     else:\n",
    "        #         i += 1\n",
    "        # return intervals\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def merge(self, intervals: List[List[int]]) -> List[List[int]]:\n",
    "        intervals.sort()\n",
    "        size=len(intervals)\n",
    "        i=0\n",
    "        while i<size-1:\n",
    "            if intervals[i][1]>=intervals[i+1][0]:\n",
    "                if intervals[i][1]<intervals[i+1][1]:\n",
    "\n",
    "                    intervals[i][1]=intervals[i+1][1]\n",
    "                del intervals[i+1]\n",
    "                i-=1\n",
    "                size-=1\n",
    "            \n",
    "            i+=1\n",
    "        return intervals"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def merge(self, intervals: List[List[int]]) -> List[List[int]]:\n",
    "        l_last = 0\n",
    "        while l_last != len(intervals):\n",
    "            l_last = len(intervals)\n",
    "            i = 0\n",
    "            while i < len(intervals):\n",
    "                p = intervals[i]\n",
    "                j = i+1\n",
    "                while j < len(intervals):\n",
    "                    q = intervals[j]\n",
    "                    if (p[1]-q[0]) * (p[0]-q[1]) <= 0:\n",
    "                        l = min(p[0], q[0])\n",
    "                        r = max(p[1], q[1])\n",
    "                        del intervals[j]\n",
    "                        intervals[i][0] = l\n",
    "                        intervals[i][1] = r \n",
    "                        j -= 1\n",
    "                    j += 1\n",
    "                i += 1\n",
    "        return intervals"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def merge(self, intervals: List[List[int]]) -> List[List[int]]:\n",
    "        if len(intervals) <= 1:\n",
    "            return intervals\n",
    "        results = [intervals[0]]\n",
    "        for i in range(1, len(intervals)):\n",
    "            item = intervals[i]\n",
    "            j = 0\n",
    "            while True:\n",
    "                if j >= len(results):\n",
    "                    break\n",
    "                if results[j][1] < item[0] or results[j][0] > item[1]:\n",
    "                    j += 1\n",
    "                    continue\n",
    "                else:\n",
    "                    item2 = results.pop(j)\n",
    "                    left, right = min(item[0], item2[0]), max(item[1], item2[1])\n",
    "                    item = [left, right]\n",
    "            results.append(item)\n",
    "        return results\n",
    "\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def merge(self, intervals: List[List[int]]) -> List[List[int]]:\n",
    "        intervals.sort()\n",
    "        res=[]\n",
    "        t=intervals[0]\n",
    "        for i in range(1,len(intervals)):\n",
    "            if t[1]>=intervals[i][0]:\n",
    "                t=[t[0],max(t[1],intervals[i][1])]\n",
    "            else:\n",
    "                res.append(t)\n",
    "                t=intervals[i]\n",
    "        res.append(t)\n",
    "        return res\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def merge(self, intervals: List[List[int]]) -> List[List[int]]:\n",
    "        intervals.sort()\n",
    "        n = len(intervals)\n",
    "        ans, res = [], []\n",
    "        temp = [intervals[0]]\n",
    "        ma = intervals[0][1]\n",
    "        for i in range(1,n):\n",
    "            if intervals[i][0] <= ma or (intervals[i][0] <= ma and intervals[i][1] <= ma):\n",
    "                ma = max(ma,intervals[i][0],intervals[i][1])\n",
    "                temp.append(intervals[i])\n",
    "            else:\n",
    "                ans.append(temp)\n",
    "                ma = intervals[i][1]\n",
    "                temp = [intervals[i]]\n",
    "        ans.append(temp)\n",
    "        for i in range(len(ans)):\n",
    "            temp1 = ans[i]\n",
    "            start = temp1[0][0]\n",
    "            ma1 = 0\n",
    "            for j in range(len(temp1)):\n",
    "                ma1 = temp1[j][1] if temp1[j][1] > ma1 else ma1\n",
    "            res.append((start,ma1))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def merge(self, intervals: List[List[int]]) -> List[List[int]]:\n",
    "        intervals.sort()\n",
    "        left = 0 \n",
    "        right = 1\n",
    "\n",
    "        while right < len(intervals):\n",
    "            left1, left2 = intervals[left][0], intervals[left][1]\n",
    "            right1, right2 = intervals[right][0], intervals[right][1]\n",
    "\n",
    "            if left2 < right1:\n",
    "                left += 1\n",
    "                right += 1\n",
    "            else:\n",
    "                intervals[right] = [left1, max(left2, right2)]\n",
    "                intervals.pop(left)\n",
    "\n",
    "        return intervals"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def merge(self, intervals: List[List[int]]) -> List[List[int]]:\n",
    "        if len(intervals)==0:\n",
    "            return intervals\n",
    "        intervals.sort(key = lambda x:x[0])\n",
    "        i = 0\n",
    "        while i < len(intervals)-1:\n",
    "            if intervals[i+1][0]<=intervals[i][1]:\n",
    "                left, right = intervals[i][0], max(intervals[i+1][1], intervals[i][1])\n",
    "                intervals.pop(i+1)\n",
    "                intervals[i] = [left, right]\n",
    "            else:\n",
    "                i+=1\n",
    "        return intervals\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def merge(self, intervals: List[List[int]]) -> List[List[int]]:\n",
    "        intervals = sorted(intervals)\n",
    "        l = 0\n",
    "        r = 1\n",
    "        while r<len(intervals):\n",
    "            x1, y1 = intervals[l]\n",
    "            x2, y2 = intervals[r]\n",
    "            if y1<x2:\n",
    "                l,r = l+1, r+1\n",
    "            else:\n",
    "                intervals[r] = x1, max(y1, y2)\n",
    "                intervals.pop(l)\n",
    "        return intervals"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def merge(self, intervals: List[List[int]]) -> List[List[int]]:\n",
    "        if not intervals:\n",
    "            return []\n",
    "        intervals.sort(key = lambda x:x[0])\n",
    "\n",
    "        m = [intervals[0]]\n",
    "        for i in range(1, len(intervals)):\n",
    "            print(intervals[i][0], m[-1][1])\n",
    "            if intervals[i][0] <= m[-1][1]:\n",
    "                m[-1][1] = max(intervals[i][1], m[-1][1])\n",
    "            else:\n",
    "                m.append(intervals[i])\n",
    "        return m\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def merge(self, intervals: List[List[int]]) -> List[List[int]]:\n",
    "        intervals.sort(key = lambda x: (x[0],x[1]))\n",
    "        res = []\n",
    "\n",
    "        for inter in intervals:\n",
    "            if not res or res[-1][1] < inter[0]:\n",
    "                res.append(inter)\n",
    "            else:\n",
    "                res[-1][1] = max(res[-1][1],inter[1])\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def merge(self, intervals: List[List[int]]) -> List[List[int]]:\n",
    "        res = []\n",
    "        intervals.sort(key=lambda num: num[0])\n",
    "        for s_i, e_i in intervals:\n",
    "            if res:\n",
    "                s_prev, e_prev = res[-1]\n",
    "                if s_i > e_prev:  # cannot merge\n",
    "                    res.append([s_i, e_i])\n",
    "                elif e_i < e_prev:\n",
    "                    continue\n",
    "                else:\n",
    "                    res[-1][1] = e_i\n",
    "            else:\n",
    "                res.append([s_i, e_i])\n",
    "        \n",
    "        return res\n",
    "            "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
